Heap's algorithm generates all possible permutations of n 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 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. The sequence of permutations of n objects generated by Heap's algorithm is the beginning of the sequence of permutations of n+1 objects. So there is one infinite sequence of permutations generated by Heap's algorithm (sequence A280318 in the OEIS).
Details of the algorithm For a collection C {\displaystyle C} 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. Described recursively as a decrease and conquer method, Heap's algorithm operates at each step on the k {\displaystyle k} initial elements of the collection. Initially k = n {\displaystyle k=n} and thereafter k < n {\displaystyle k<n} . Each step generates the k ! {\displaystyle k!} permutations that end with the same n − k {\displaystyle n-k} final elements. It does this by calling itself once with the k th {\displaystyle k{\text{th}}} element unaltered and then k − 1 {\displaystyle k-1} times with the ( k th {\displaystyle k{\text{th}}} ) element exchanged for each of the initial k − 1 {\displaystyle k-1} elements. The recursive calls modify the initial k − 1 {\displaystyle k-1} 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 k {\displaystyle k} is even, then the final element is iteratively exchanged with each element index. If k {\displaystyle k} is odd, the final element is always exchanged with the first.
One can also write the algorithm in a non-recursive format.
Proof 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. Since 1 is odd, this is what was claimed, so the claim is true for arrays of length 1. 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. The first swap puts element l (the last element) in position 0, and element 0 in position l. The next swap puts the element in position l (where the previous iteration put original element 0) in position 1 and element 1 in position l. In the penultimate iteration, the swap puts element l-1 in position l, and the element in position l (where the previous iteration put original element l-2) in position l-1. In the final iteration, the swap exchanges position l with itself and therefore leaves the array unchanged. To illustrate the above, look below for the case n = 4.
1,2,3,4 ... original array 1,2,3,4 ... 1st iteration (permute subarray) 4,2,3,1 ... 1st iteration (swap 1st element into last position) 4,2,3,1 ... 2nd iteration (permute subarray) 4,1,3,2 ... 2nd iteration (swap 2nd element into last position) 4,1,3,2 ... 3rd iteration (permute subarray) 4,1,2,3 ... 3rd iteration (swap 3rd element into last position) 4,1,2,3 ... 4th iteration (permute subarray) 4,1,2,3 ... 4th iteration (swap 4th element into last position) The altered array is a rotated version of the original
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. Doing permutations(l+1, A) will in each iteration i of the for-loop, first do permutations(l, A) (rotating the first l elements of A by 1 position since l is even) and then, swap the elements in positions 0 and l (the last position) in A. Rotating the first l elements and then swapping the first and last elements is equivalent to rotating the entire array. Since there are as many iterations of the loop as there are elements in the array, the entire array is rotated until each element returns to where it started. To illustrate the above, look below for the case n = 5.
… excerpt ends here. Continue reading the full article.
