Heap's algorithm
Heap's algorithm generates all possible permutations of objects. It was first proposed by B. R. Heap in 1963. The algorithm minimizes movement: it generates each permutation from the previous one by interchanging a single pair of elements; the other elements are not disturbed. 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. The sequence of permutations of objects generated by Heap's algorithm is the beginning of the sequence of permutations of objects. So there is one infinite sequence  of permutations generated by Heap's algorithm . Details of the algorithm. For a collection formula_1 containing 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. Described recursively as a decrease and conquer method, Heap's algorithm operates at each step on the formula_2 initial elements of the collection. Initially formula_3 and thereafter formula_4. Each step generates the formula_5 permutations that end with the same formula_6 final elements. It does this by calling itself once with the formula_7 element unaltered  and then formula_8 times with the (formula_7) element exchanged for each of the initial formula_8 elements. The recursive calls modify the initial formula_8 elements and a rule is needed at each iteration to select which will be exchanged with the last. Heap's method says that this choice can be made by the parity of the number of elements operated on at this step. If formula_2 is even, then the final element is iteratively exchanged with each element index. If formula_2 is odd, the final element is always exchanged with the first. procedure generate(k : integer, A : array of any): One  can also write the algorithm in a non-recursive format. procedure generate(n : integer, A : array of any): Proof. In this proof, we'll use the implementation below as Heap's Algorithm. While it is not optimal (see section below), the implementation is nevertheless still correct and will produce all permutations. The reason for using the below implementation is that the analysis is easier, and certain patterns can be easily illustrated. procedure generate(k : integer, A : array of any): Claim: If array has length , then performing Heap's algorithm will either result in being "rotated" to the right by 1 (i.e. each  element is shifted to the right with the last element occupying the first position) or result in being unaltered, depending if is even or odd, respectively. Basis: The claim above trivially holds true for formula_14 as Heap's algorithm will simply return unaltered in order. Induction: Assume the claim holds true for some formula_15. We will then need to handle two cases for formula_16: formula_16 is even or odd. If, for , formula_18 is even, then the subset of the first elements will remain unaltered after performing Heap's Algorithm on the subarray, as assumed by the induction hypothesis. By performing  Heap's Algorithm on the subarray and then performing the swapping operation, in the th iteration of the for-loop, where formula_19, the th element in will be swapped into the last position of which can be thought as a kind of "buffer". By swapping the 1st and last element, then swapping 2nd and last, all the way until the th and last elements are swapped, the array will at last experience a rotation. To illustrate the above, look below for the case formula_20 If, for , formula_18 is odd, then the subset of the first elements will be rotated after  performing Heap's Algorithm on the first elements. Notice that, after 1 iteration of the for-loop, when performing Heap's Algorithm on , is rotated to the right by 1. By the induction hypothesis, it is assumed that the first elements will rotate. After this rotation, the first element of will be swapped into the buffer which, when combined with the previous rotation operation, will in essence perform a rotation on the array. Perform this rotation operation times, and the array will revert to its original state. This is illustrated below for the case formula_22. The induction proof for the  claim is now complete, which will now lead to why Heap's Algorithm creates all permutations of array . Once again we will prove by induction the correctness of Heap's Algorithm. Basis: Heap's Algorithm trivially permutes an array of size as outputting is the one and only permutation of . Induction: Assume Heap's Algorithm permutes an array of size . Using the results from the previous proof, every element of will be in the "buffer" once when the first elements are permuted. Because permutations of an array can be made by altering some array through the removal of an element  from then tacking on to each permutation of the altered array, it follows that Heap's Algorithm permutes an array of size formula_16, for the "buffer" in essence holds the removed element, being tacked onto the permutations of the subarray of size . Because each iteration of Heap's Algorithm has a different element of occupying the buffer when the subarray is permuted, every permutation is generated as each element of has a chance to be tacked onto the permutations of the array without the buffer element. Frequent mis-implementations. It is tempting to simplify the recursive version given above by  reducing the instances of recursive calls. For example, as: procedure generate(k : integer, A : array of any): This implementation will succeed in producing all permutations but does not minimize movement. As the recursive call-stacks unwind, it results in additional swaps at each level. Half of these will be no-ops of formula_24 and formula_25 where formula_26 but when formula_2 is odd, it results in additional swaps of the formula_28 with the formula_29 element. These additional swaps significantly alter the order of the formula_8 prefix elements. The additional swaps can be avoided by either adding an additional recursive call before the  loop and looping formula_8 times (as above) or looping formula_2 times and checking that formula_33 is less than formula_8 as in: procedure generate(k : integer, A : array of any): The choice is primarily aesthetic but the latter results in checking the value of formula_33 twice as often.