Heap's algorithm

Heap's algorithm is an algorithm for generating permutations. It was first proposed by B. R. Heap in 1963.^[1] It interchanges positions of elements to generate the next permutation. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was in practical terms the fastest algorithm for then-current computers.^[2]

Details of algorithm

Suppose we have a sequence of different characters with a length of N. Heap found that we can simply interchange the positions of two elements to get a new permutation output. Let us describe it in a recursive way. If we have got (N − 1)! permutation outputs, fixing the last element. Then if N is odd, we can switch the first element and the last one, while N is even we can switch the ith (i is the step number of the cycle, and now it is 1) element and the last one, then we will continue outputting the (N − 1)! permutation outputs and switching step for another N − 1 times(N times int total). The following pseudocode outputs permutations of a data array of length N.

procedure generate(N : integer, data : array of any):
    if N = 1 then
        output(data)
    else
        for c := 1; c <= N; c += 1 do
            generate(N - 1, data)
            swap(data[if N is odd then 1 else c], data[N])

One could also use rewrite the algorithm in a non-recursive method.^[3]

References

1. Heap, B. R. (1963). "Permutations by Interchanges" (PDF). The Computer Journal. 6 (3): 293–4.
2. Attention: This template ({{cite doi}}) is deprecated. To cite the publication identified by doi:10.1145/356689.356692, please use {{cite journal}} (if it was published in a bona fide academic journal, otherwise {{cite report}} with |doi=10.1145/356689.356692 instead.
3. Sedgewick, Robert. "a talk on Permutation Generation Algorithms" (PDF).