Content deleted Content added
Tag: gettingstarted edit |
Fix a pseudocode comment in the non-recursive implementation.The previous version implies that c[1] encodes |
||
| (237 intermediate revisions by more than 100 users not shown) | |||
Line 1:
{{Short description|Method of generating all permutations of n objects}}
{{Distinguish|heapsort}}
[[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)]]
[[File:Wheel diagram Heap's algorithm.svg|thumb|Wheel diagram of all permutations of length <math>n=4</math> generated by Heap's algorithm, where each permutation is color-coded (1=blue, 2=green, 3=yellow, 4=red).]]
'''Heap's
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 ==
For a collection <math>C</math> 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.
Described recursively as a [[Divide-and-conquer algorithm|decrease and conquer]] method, Heap's algorithm operates at each step on the <math>k</math> initial elements of the collection. Initially <math>k=n</math> and thereafter <math>k<n</math>. Each step generates the <math>k!</math> permutations that end with the same <math>n-k</math> final elements. It does this by calling itself once with the <math>k\text{th}</math> element unaltered and then <math>k-1</math> times with the (<math>k\text{th}</math>) element exchanged for each of the initial <math>k-1</math> elements. The recursive calls modify the initial <math>k-1</math> 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 (mathematics)|parity]] of the number of elements operated on at this step. If <math>k</math> is even, then the final element is iteratively exchanged with each element index. If <math>k</math> is odd, the final element is always exchanged with the first.
<syntaxhighlight lang="pascal">
// Output the k! permutations of A in which the first k elements are permuted in all ways.
// To get all permutations of A, use k := length of A.
//
// If, k > length of A, will try to access A out of bounds.
// If k <= 0 there will be no output (empty array has no permutations)
procedure permutations(k : integer, A : array of any):
if k = 1 then
output(A)
else
// permutations with last element swapped out
for i := 0; i < k-1; i += 1 do
if k is even then
swap(A[i], A[k-1])
else
swap(A[0], A[k-1])
end if
permutations(k - 1, A)
end for
end if
</syntaxhighlight>
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|date=4 June 2020 |url=https://sedgewick.io/wp-content/uploads/2022/03/2002PermGeneration.pdf}}</ref>
<syntaxhighlight lang="pascal">
procedure permutations(n : integer, A : array of any):
// c is an encoding of the stack state.
// c[k] encodes the for-loop counter for when permutations(k + 1, A) is called
c : array of int
for i := 0; i < n; i += 1 do
c[i] := 0
end for
output(A)
// i acts similarly to a stack pointer
i := 1;
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)
// Swap has occurred ending the while-loop. Simulate the increment of the while-loop counter
c[i] += 1
// Simulate recursive call reaching the base case by bringing the pointer to the base case analog in the array
i := 1
else
// Calling permutations(i+1, A) has ended as the while-loop terminated. Reset the state and simulate popping the stack by incrementing the pointer.
c[i] := 0
i += 1
end if
end while
</syntaxhighlight>
==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.
<syntaxhighlight lang="pascal">
// Output the k! permutations of A in which the first k elements are permuted in all ways.
// To get all permutations of A, use k := length of A.
//
// If, k > length of A, will try to access A out of bounds.
// If k <= 0 there will be no output (empty array has no permutations)
procedure permutations(k : integer, A : array of any):
if k = 1 then
output(A)
else
for i := 0; i < k; i += 1 do
permutations(k - 1, A)
if k is even then
swap(A[i], A[k-1])
else
swap(A[0], A[k-1])
end if
end for
end if
</syntaxhighlight>
Claim: If array A has length {{mvar|n}}, then <code>permutations(n, A)</code> will result in either A being unchanged, if {{mvar|n}} is odd, or, if {{mvar|n}} is even, then A is rotated to the right by 1 (last element shifted in front of other elements).
Base: If array {{mvar|A}} has length 1, then <code>permutations(1, A)</code> 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 {{math|l}} ≥ 1, then we show that the claim is true for arrays of length {{math|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 {{math|l}} is odd or even, we prove each case separately.
If {{math|l}} is odd, then, by the induction hypothesis, for an array A of length {{math|l}}, <code>permutations(l, A)</code> will not change A, and for the claim to hold for arrays of length {{math|l}}+1 (which is even), we need to show that <code>permutations(l+1, A)</code> rotates A to the right by 1 position. Doing <code>permutations(l+1, A)</code> will first do <code>permutations(l, A)</code> (leaving A unchanged since {{math|l}} is odd) and then in each iteration {{math|i}} of the for-loop, swap the elements in positions {{math|i}} and {{math|l}} (the last position) in A. The first swap puts element {{math|l}} (the last element) in position 0, and element 0 in position {{math|l}}. The next swap puts the element in position {{math|l}} (where the previous iteration put original element 0) in position 1 and element 1 in position {{math|l}}. In the final iteration, the swap puts element {{math|l}}-1 is in position {{math|l}}, and the element in position {{math|l}} (where the previous iteration put original element {{math|l}}-2) in position {{math|l}}-1. To illustrate the above, look below for the case {{math|n}} = 4.
<pre>
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
</pre>
If {{math|l}} is even, then, by the induction hypothesis, for an array A of length {{math|l}}, <code>permutations(l, A)</code> rotates A to the right by 1 position, and for the claim to hold for arrays of length {{math|l}}+1 (which is odd), we need to show that <code>permutations(l+1, A)</code> leaves A unchanged. Doing <code>permutations(l+1, A)</code> will in each iteration {{math|i}} of the for-loop, first do <code>permutations(l, A)</code> (rotating the first {{math|l}} elements of A by 1 position since {{math|l}} is even) and then, swap the elements in positions 0 and {{math|l}} (the last position) in A. Rotating the first {{math|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 {{math|n}} = 5.
<pre>
1,2,3,4,5 ... original array
4,1,2,3,5 ... 1st iteration (permute subarray, which rotates it)
5,1,2,3,4 ... 1st iteration (swap)
3,5,1,2,4 ... 2nd iteration (permute subarray, which rotates it)
4,5,1,2,3 ... 2nd iteration (swap)
2,4,5,1,3 ... 3rd iteration (permute subarray, which rotates it)
3,4,5,1,2 ... 3rd iteration (swap)
1,3,4,5,2 ... 4th iteration (permute subarray, which rotates it)
2,3,4,5,1 ... 4th iteration (swap)
5,2,3,4,1 ... 5th iteration (permute subarray, which rotates it)
1,2,3,4,5 ... 5th iteration (swap)
The final state of the array is in the same order as the original
</pre>
The induction proof for the claim is now complete, which will now lead to why Heap's Algorithm creates all permutations of array {{mvar|A}}. Once again we will prove by induction the correctness of Heap's Algorithm.
Basis: Heap's Algorithm trivially permutes an array {{mvar|A}} of size {{mvar|1}} as outputting {{mvar|A}} is the one and only permutation of {{mvar|A}}.
Induction: Assume Heap's Algorithm permutes an array of size {{mvar|i}}. Using the results from the previous proof, every element of {{mvar|A}} will be in the "buffer" once when the first {{mvar|i}} elements are permuted. Because permutations of an array can be made by altering some array {{mvar|A}} through the removal of an element {{mvar|x}} from {{mvar|A}} then tacking on {{mvar|x}} to each permutation of the altered array, it follows that Heap's Algorithm permutes an array of size <math>i+1</math>, for the "buffer" in essence holds the removed element, being tacked onto the permutations of the subarray of size {{mvar|i}}. Because each iteration of Heap's Algorithm has a different element of {{mvar|A}} occupying the buffer when the subarray is permuted, every permutation is generated as each element of {{mvar|A}} has a chance to be tacked onto the permutations of the array {{mvar|A}} 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:
<syntaxhighlight lang="pascal">
procedure permutations(k : integer, A : array of any):
if k = 1 then
output(A)
else
// Recursively call once for each k
for i := 0; i < k; i += 1 do
permutations(k - 1, A)
// swap choice dependent on parity of k (even or odd)
if k is even then
// no-op when i == k-1
swap(A[i], A[k-1])
else
// XXX incorrect additional swap when i==k-1
swap(A[0], A[k-1])
end if
end for
end if
</syntaxhighlight>
This implementation will succeed in producing all permutations but does not minimize movement. As the recursive [[Call stack|call-stacks]] unwind, it results in additional swaps at each level. Half of these will be [[Null function|no-ops]] of <math>A[i]</math> and <math>A[k-1]</math> where <math>i==k-1</math> but when <math>k</math> is odd, it results in additional swaps of the <math>kth</math> with the <math>0th</math> element.
{| class="wikitable"
|-
! <math>n</math> !! <math>n!-1</math> !! swaps !! additional = swaps <math>- (n!-1)</math>
|-
| 1 || 0 || 0 || 0
|-
| 2 || 1 || 1 || 0
|-
| 3 || 5 || 6 || 1
|-
| 4 || 23 || 27 || 4
|-
| 5 || 119 || 140 || 21
|-
| 6 || 719 || 845 || 126
|-
| 7 || 5039 || 5922 || 883
|-
| 8 || 40319 || 47383 || 7064
|-
| 9 || 362879 || 426456 || 63577
|-
|}
These additional swaps significantly alter the order of the <math>k-1</math> prefix elements.
The additional swaps can be avoided by either adding an additional recursive call before the loop and looping <math>k-1</math> times (as above) '''or''' looping <math>k</math> times and checking that <math>i</math> is less than <math>k-1</math> as in:
<syntaxhighlight lang="pascal">
procedure permutations(k : integer, A : array of any):
if k = 1 then
output(A)
else
// Recursively call once for each k
for i := 0; i < k; i += 1 do
permutations(k - 1, A)
// avoid swap when i==k-1
if (i < k - 1)
// swap choice dependent on parity of k
if k is even then
swap(A[i], A[k-1])
else
swap(A[0], A[k-1])
end if
end if
end for
end if
</syntaxhighlight>
The choice is primarily aesthetic but the latter results in checking the value of <math>i</math> twice as often.
==See also==
* [[Steinhaus–Johnson–Trotter algorithm]]
==References==
| |||