Examine individual changes

'[[File:Heap algorithm with 4 elements.svg|thumb|90px|A map of the 24 permutations and the 23 swaps used in Heap's algorithm permuting the four letters A (amber), B (blue), C (cyan) and D (dark red)]] '''Heap's [[algorithm]]''' generates all possible [[permutation]]s of {{math|''n''}} objects. It was first proposed by B. R. Heap in 1963.<ref name="Heap">{{cite journal|last=Heap|first=B. R.|title=Permutations by Interchanges|journal=The Computer Journal|year=1963|volume=6|issue=3|pages=293–4|url=http://comjnl.oxfordjournals.org/content/6/3/293.full.pdf|doi=10.1093/comjnl/6.3.293}}</ref> The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other {{math|''n''−2}} elements are not disturbed. In a 1977 review of permutation-generating algorithms, [[Robert Sedgewick (computer scientist)|Robert Sedgewick]] concluded that it was at that time the most effective algorithm for generating permutations by computer.<ref>{{Cite journal | last1 = Sedgewick | first1 = R. | title = Permutation Generation Methods | doi = 10.1145/356689.356692 | journal = ACM Computing Surveys | volume = 9 | issue = 2 | pages = 137–164| year = 1977 | pmid = | pmc = }}</ref> The sequence of permutations of {{math|''n''}} objects generated by Heap's algorithm is the beginning of the sequence of permutations of {{math|''n''+1}} objects. So there is one infinite sequence of permutations generated by Heap's algorithm {{OEIS|A280318}}. == Details of the algorithm == Suppose we have a permutation containing {{math|''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 {{math|''i''}} to 0. Now we perform the following steps repeatedly until {{math|''i''}} is equal to {{math|''n''}}. We use the algorithm to generate the {{math|(''n''−1)!}} permutations of the first {{math|''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 {{math|''n''}} is odd, we switch the first element and the last one, while if {{math|''n''}} is even we can switch the {{math|''i''}}th element and the last one (there is no difference between {{math|''n''}} even and odd in the first iteration). We add one to the counter {{math|''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 {{math|''n''}}. <source lang="pascal"> 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[i], A[n-1]) else swap(A[0], A[n-1]) end if end for generate(n - 1, A) end if </source> One can also write the algorithm in a non-recursive format.<ref>{{cite web|last=Sedgewick|first=Robert|title=a talk on Permutation Generation Algorithms|url=http://www.cs.princeton.edu/~rs/talks/perms.pdf}}</ref> <source lang="pascal"> procedure generate(n : integer, A : array of any): c : array of int for i := 0; i < n; i += 1 do c[i] := 0 end for output(A) i := 0; 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) c[i] += 1 i := 0 else c[i] := 0 i += 1 end if end while </source> ==See also== * [[Steinhaus–Johnson–Trotter algorithm]] ==References== {{Reflist}} [[Category:Combinatorial algorithms]] [[Category:Permutations]]'