Heap's algorithm

Heap's algorithm generates all possible permutations of n objects.

[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.

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.

Described recursively as a decrease and conquer method, Heap's algorithm operates at each step on the

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.

[3] In this proof, we'll use the below implementation as Heap's algorithm as it makes the analysis easier, and certain patterns can be easily illustrated.

While it is not optimal (it does not minimize moves, which is described in the section below), the implementation is correct and will produce all permutations.

Claim: If array A has length n, then permutations(n, A) will result in either A being unchanged, if n is odd, or, if n is even, then A is rotated to the right by 1 (last element shifted in front of other elements).

Base: If array A has length 1, then permutations(1, A) will output A and stop, so A is unchanged.

Induction: If the claim is true for arrays of length l ≥ 1, then we show that the claim is true for arrays of length l+1 (together with the base case this proves that the claim is true for arrays of all lengths).

Since the claim depends on whether l is odd or even, we prove each case separately.

If l is odd, then, by the induction hypothesis, for an array A of length l, permutations(l, A) will not change A, and for the claim to hold for arrays of length l+1 (which is even), we need to show that permutations(l+1, A) rotates A to the right by 1 position.

Doing permutations(l+1, A) will first do permutations(l, A) (leaving A unchanged since l is odd) and then in each iteration i of the for-loop, swap the elements in positions i and l (the last position) in A.

If l is even, then, by the induction hypothesis, for an array A of length l, permutations(l, A) rotates A to the right by 1 position, and for the claim to hold for arrays of length l+1 (which is odd), we need to show that permutations(l+1, A) leaves A unchanged.

The induction proof for the claim is now complete, which will now lead to why Heap's Algorithm creates all permutations of array A.

Once again we will prove by induction the correctness of Heap's Algorithm.

Induction: Assume Heap's Algorithm permutes an array of size i.

, for the "buffer" in essence holds the removed element, being tacked onto the permutations of the subarray of size i.

Because each iteration of Heap's Algorithm has a different element of A occupying the buffer when the subarray is permuted, every permutation is generated as each element of A has a chance to be tacked onto the permutations of the array A without the buffer element.

For example, as: 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.

These additional swaps significantly alter the order of the

as in: The choice is primarily aesthetic but the latter results in checking the value of