Misplaced Pages

This is an old revision of this page, as edited by Sverdrup (talk | contribs) at 00:04, 7 July 2015 (This edit broke the algorithm -- undo to restore. Undid revision 670122498 by 120.56.132.183 (talk)). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Heap's algorithm is an algorithm used for generating all possible permutations of some given length. It was first proposed by B. R. Heap in 1963. It generates each permutation from the previous one by choosing a pair of elements to interchange. In a 1977 review of permutation-generating algorithms, Robert Sedgewick concluded that it was at that time the most effective algorithm for generating permutations by computer.

Details of the algorithm

Suppose we have a permutation containing N different elements. Heap found a systematic method for choosing at each step a pair of elements to switch, in order to produce every possible permutation of these elements exactly once. Let us describe Heap's method in a recursive way. First we set a counter i  to 0. Now we perform the following steps repeatedly, until i  is bigger than N. We use the algorithm to generate the (N − 1)! permutations of the first N − 1 elements, adjoining the last element to each of these. This generates all of the permutations that end with the last element. Then if N is odd, we switch the first element and the last one, while if N is even we can switch the i th element and the last one (there is no difference between N even and odd in the first iteration). We add one to the counter i and repeat. In each iteration, the algorithm will produce all of the permutations that end with the element that has just been moved to the "last" position. The following pseudocode outputs all permutations of a data array of length N.

procedure generate(n : integer, A : array of any):
    if n = 1 then
          output(A)
    else
        for i := 0; i < n - 1; i += 1 do
            generate(n - 1, A)
            if n is even then
                swap(A, A)
            else
                swap(A, A)
            end if
        end for
        generate(n - 1, A)
    end if

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

See also

• Steinhaus–Johnson–Trotter algorithm

References

1. Heap, B. R. (1963). "Permutations by Interchanges" (PDF). The Computer Journal. 6 (3): 293–4. doi:10.1093/comjnl/6.3.293.
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).

• Combinatorial algorithms
• Permutations