can someone explain why does Heap's Algorithm uses a condition statement checking for K whether it is even or odd and the swaps are different in each one? i can't find any intuitive explanation on the Internet
this code is from Wikipedia
procedure generate(k : integer, A : array of any):
if k = 1 then
output(A)
else
// Generate permutations with kth unaltered
// Initially k == length(A)
generate(k - 1, A)
// Generate permutations for kth swapped with each k-1 initial
for i := 0; i < k-1; i = 1 do
// Swap choice dependent on parity of k (even or odd)
if k is even then
swap(A[i], A[k-1]) // zero-indexed, the kth is at k-1
else
swap(A[0], A[k-1])
end if
generate(k - 1, A)
end for
end if
CodePudding user response：
You can't really disentangle the reason that you change swapping behavior based on k's parity from the explanation/justification for why the algorithm works as a whole, and that is a complicated thing to demonstrate, but basically, it relates to the different side-effects generate has on the underlying array depending on whether k is even or odd, and leveraging those side effects in an alternating fashion to explore the whole permutation space. These side-effects and their interactions are a bit mathematically complicated, so, to simplify the discussion, first I'm going to re-write the algorithm into a completely a equivalent form that will be easier to reason about. Rather than putting the first call to generate outside of the for loop and iterating from 0 to k-1, we put it inside, iterate from 0 to k, and break out of the last iteration early (to avoid unnecessary swaps after all output for the current k value has already been generated).
procedure generate(k : integer, A : array of any):
if k = 1:
output(A)
else:
for i := 0; i < k; i = 1 do:
generate(k - 1, A)
if i 1 = k:
break
if k is even:
swap(A[i], A[k-1])
else:
swap(A[0], A[k-1])
However, letting the unnecessary swaps occur on the tail-end of the final loop iterations by removing the break statement produces the same permutations (albeit in a different order), and makes the side-effects of each iteration of the program significantly easier to reason about:
procedure generate(k : integer, A : array of any):
if k = 1:
output(A)
else:
for i := 0; i < k; i = 1 do:
generate(k - 1, A)
if k is even:
swap(A[i], A[k-1])
else:
swap(A[0], A[k-1])
With that out of the way, here's the basic idea of Heap's algorithm (in any form):
Calling the generate function with a given k value is meant to permute the first k elements of the array (everything from index k and beyond is necessarily fixed, because no swaps involve indices exceeding k-1). To permute these first k elements, we're making k recursive calls to generate(k-1, A), and before each of these recursive calls are made, we want to swap a unique element from the segment we are permuting to its end (that is into the kth position: index k-1), because putting a different element on the back of all size k-1 permutations effectively generates all size k permutations. The conditional choice of where we swap from to pick this unique element is dictated purely by the different side effects calling generate(k-1, A) has on the underlying array depending on whether k-1 is even or odd, but the point is the same: to pick an element we haven't used yet in the for loop and swap it back to the kth position of the array before we generate the next batch of size k-1 permutations.
The reason these swaps work in this amended version of the algorithm are actually pretty simple. The side effect of calling generate(k-1, A) where k-1 is even is to rotate those first k-1 elements of the array one position to the right, and calls to generate(k-1, A) with odd k-1 actually have no side effects in terms of element order: the first k-1 elements of the array end up exactly where they were before the call was made.
For an example in the even k case, if we call generate(4, A) successively on the array [1,2,3,4,5,...], the first 4 elements cycle like this (and everything following them is fixed):
[1,2,3,4,...]
[4,1,2,3,...]
[3,4,1,2,...]
[2,3,4,1,...]
[1,2,3,4,...]
...
If we call generate(5, A) on [1,2,3,4,5,6,...], the side effect in terms of the array's order is a no-op (All permutations of the first 5 elements are still being generated from the recursive calls, it's just that the extra swaps made when we remove the break statement cancel out the ordering side effects).
[1,2,3,4,5,6,...]
[1,2,3,4,5,6,...]
...
The conditional swap strategy comes directly out of these facts:
When k is even we're calling generate(k-1, A) with an odd value, which has no ordering side effect, so if we want to pick a different element each iteration to swap to the back we can just use swap(A[i], A[k-1]), as i increments each iteration and the other elements aren't moving.
On the other hand, when k is odd, we're calling generate(k-1, A) with an even value, which has the side effect of rotating elements one step to the right. That is why we simply pull from A[0] repeatedly: the side effects of the even calls to generate in the loop do the work of cycling elements for us: we can just grab elements from the first position every time because the side-effects put a different element into that position at each iteration.
Basically, if we want to grab every one of the first k elements across our for loop and they're statically positioned, we have to use every value of i, and if they're cycling already, we have to grab from the same position every time. Whether they're statically positioned or cycling already depends on the different ordering side-effects generate has based on whether k is even or odd. The mathematics of the side-effects for even/odd k, the cycles those side-effects produce, and the reasoning behind why these particular rules work changes a bit when you add the break back, but the same rules still work and the general form of the analysis you have to do to prove that also remains the same.