Permutations - rFronteddu/general_wiki GitHub Wiki

Heap's algorithm generates all possible permutations of n objects. It was first proposed by B. R. Heap in 1963.[1] The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other n−2 elements are not disturbed.

Proof

Described recursively as a decrease and conquer method, Heap's algorithm operates at each step on the k initial elements of the collection. Initially, k = n and thereafter k < n. Each step generates the k! permutations that end with the same n − k final elements. It does this by calling itself once with the kth element unaltered and then k − 1 times with the (k_th) element exchanged for each of the initial k − 1 elements. The recursive calls modify the initial k − 1 elements and a rule is needed at each iteration to select which will be exchanged with the last. Heap's method says that the parity can make this choice of the number of elements operated on at this step. If k is even, then the final element is iteratively exchanged with each element index. If k is odd, the final element is always exchanged with the first.

// Output the k! permutations of A in which the first k elements are permuted in all ways.
// To get all permutations of A, use k := length of A.
//
// If, k > length of A, will try to access A out of bounds.
// If k <= 0 there will be no output (empty array has no permutations)
procedure permutations(k : integer, A : array of any):
    if k = 1 then
        output(A)
    else
        // permutations with last element fixed
        permutations(k - 1, A)
        // permutations with last element swapped out
        for i := 0; i < k-1; i += 1 do
            if k is even then
                swap(A[i], A[k-1])
            else
                swap(A[0], A[k-1])
            end if
            permutations(k - 1, A)
        end for
   

 end if

One can also write the algorithm in a non-recursive format.

procedure permutations(n : integer, A : array of any):
    // c is an encoding of the stack state.
    // c[k] encodes the for-loop counter for when permutations(k - 1, A) is called
    c : array of int

    for i := 0; i < n; i += 1 do
        c[i] := 0
    end for

    output(A)
    
    // i acts similarly to a stack pointer
    i := 1;
    while i < n do
        if  c[i] < i then
            if i is even then
                swap(A[0], A[i])
            else
                swap(A[c[i]], A[i])
            end if
            output(A)
            // Swap has occurred ending the while-loop. Simulate the increment of the while-loop counter
            c[i] += 1
            // Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
            i := 1
        else
            // Calling permutations(i+1, A) has ended as the while-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
            c[i] := 0
            i += 1
        end if
    end while