Understanding Recursion to Generate Permutations

Understanding Recursion to generate permutations

PaulR has the right suggestion. You have to run through the code by "hand" (using whatever tools you want - debuggers, paper, logging function calls and variables at certain points) until you understand it. For an explanation of the code I'll refer you to quasiverse's excellent answer.

Perhaps this visualization of the call graph with a slightly smaller string makes it more obvious how it works:

The graph was made with graphviz.

// x.dot
// dot x.dot -Tpng -o x.png
digraph x {
rankdir=LR
size="16,10"

node [label="permute(\"ABC\", 0, 2)"] n0;
 node [label="permute(\"ABC\", 1, 2)"] n1;
  node [label="permute(\"ABC\", 2, 2)"] n2;
  node [label="permute(\"ACB\", 2, 2)"] n3;
 node [label="permute(\"BAC\", 1, 2)"] n4;
  node [label="permute(\"BAC\", 2, 2)"] n5;
  node [label="permute(\"BCA\", 2, 2)"] n6;
 node [label="permute(\"CBA\", 1, 2)"] n7;
  node [label="permute(\"CBA\", 2, 2)"] n8;
  node [label="permute(\"CAB\", 2, 2)"] n9;

n0 -> n1 [label="swap(0, 0)"];
n0 -> n4 [label="swap(0, 1)"];
n0 -> n7 [label="swap(0, 2)"];

n1 -> n2 [label="swap(1, 1)"];
n1 -> n3 [label="swap(1, 2)"];

n4 -> n5 [label="swap(1, 1)"];
n4 -> n6 [label="swap(1, 2)"];

n7 -> n8 [label="swap(1, 1)"];
n7 -> n9 [label="swap(1, 2)"];
}

Recursive function to generate permutations correctly prints each permutation but can not add it to a list

You append perm to permutations then remove the elements in perm using pop(). This will remove those in permutations as it is not a copy of perm that is present in permutations but it is a reference to perm itself.

The concept of references, is similar to pointers in C.

object_1 = object_2

saves a reference of object_2 to object_1 not a copy so any change in object_2 will reflect in object_1

use copy.deepcopy() to copy the list perm

Working code:

import copy
permutations = []

def generate_permutations(n, perm=[]):
    """
    Recursive function to print all possible permutations of integers in range n.
    :param perm: list representing a single permutation of integers in range(n)
    :param n: end of range(n) and length of each permutation
    """
    # base case: when a permutation reaches its full length, print it and move on:
    if len(perm) == n:
        print(perm)
        permutations.append(copy.deepcopy(perm))  
        return
    # recursive case:
    for k in range(n):
        # if number k not already in the permutation, add it, generate permutations, and
        # then remove k so a new set of permutations can be generated.
        if k not in perm:
            perm.append(k)
            generate_permutations(n, perm)
            perm.pop()

generate_permutations(3)
print(permutations)

Output:

[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
[[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]]

How does recursion work in a permutation?

Let's look at what the first call generates:

("" + str.charAt(0), str.substring(0, 0) + str.substring(0 + 1))
p("C", "AT")

("" + str.charAt(1), str.substring(0,1) + str.substring(1 + 1))
p("A", "CT")

("" + str.charAt(2), str.substring(0, 2) + str.substring(2 + 1))
p("T", "CA")

Each call extracts each letter of str and adds it to the current prefix. The first call puts each letter of the original string as the start of a permutation. Then, for each such permutation, the algorithm extracts each letter of the remaining suffix and adds it to the accumulating prefix, so that all possibilities are explored:

C AT
    CA T
    CT A
        "CAT"
        "CTA"

A CT
    AC T
    AT C
        "ACT"
        "ATC"

T CA
    TC A
    TA C
         "TCA"
         "TAC"

Recursive permutation

Here is the code in Prolog

permutate(As,[B|Cs]) :- select(B, As, Bs), permutate(Bs, Cs).
select(A, [A|As], As).
select(A, [B|Bs], [B|Cs]) :- select(A, Bs, Cs).

?- permutate([a,b,c], P).

Pascal is much harder.

Here is an usefull algorithm, you might want to use. But it is not tested, so you have to debug it yourself. So you have to know how the algorithm works.

The Bell Permutation algorithm: http://programminggeeks.com/bell-algorithm-for-permutation/

procedure permutate(var numbers: array [1..100] of integer; size: integer; 
                    var pos, dir: integer)
begin
  if pos >= size then
  begin
     dir = -1 * dir;
     swap(numbers, 1, 2);
  end
  else if pos < 1 then 
  begin
     dir = -1 * dir;
     swap(numbers, size-1, size);
  end
  else
  begin
     swap(numbers, pos, pos+1);
  end;
  pos = pos + dir;
end;

begin
    var a, b: integer;
    a = 1; b = 1;
    while true do
    begin
       permutate(A, 5, a, b);
       printArray(A, 5);
    end;
end.

I don't understand this recursive method in python to generate permutations

The code has the following idea: Deliver all permutations by choosing one element from the input and then deliver all permutations of the remaining elements, prepended by the chosen element. After this, repeat with another element.

So, if you have as input [0, 1, 2], then the code uses the first element (0) and builds all permutations of the remaining elements (1 and 2). (These permutations are [1, 2] and [2, 1] of course.)

Then it delivers (yields) the 0 prepended to [1, 2] and then the 0 prepended to [2, 1], i. e. [0, 1, 2] and [0, 2, 1].

Then it continues and chooses the next element (1). It then builds the permutations of the remaining elements (0, 2) (i. e. [0, 2] and [2, 0]).

And so forth.

Generating all permutations of a given string

public static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(via Introduction to Programming in Java)

---

Related Topics