Good day. Some time ago I found a page on (en.) wikipedia about Heap's algorithm for permutations. Here it is.
Original algorithm can be written as next (copy from (en.) wikipedia):
procedure generate(k : integer, A : array of any): if k = 1 then output(A) else for i := 0; i < k; i += 1 do generate(k - 1, A) if k is even then swap(A[i], A[k-1]) else swap(A, A[k-1]) end if end for end if
So we have two different ways of how algorithm works with odd and even value of k.
When we use "even way" - the set, which we permute, is been shifted to the right with a cycle. So [1, 2, 3, 4] -> will become [4, 1, 2, 3]
When we use "odd way" (for some k = a > 1) - we reduce previous cyclic shifts to the right, that were caused by recursive calls of original algorithm in a "for" cycle. So [1, 2, 3, 4, 5] -> will stay [1, 2, 3, 4, 5]
That how original algorithm works, "even way" creates shifts, "odd way" reduce it, so upper "even way" may change set, in way that upper "odd way" may also reduce it.
Now about optimization (also from (en.) wikipedia):
procedure generate(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 generate(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, A[k-1]) end if end if end for end if
The optimization consists in removing "extra" permutations. When algorithm uses "even way" the optimization doesn't change logic and result. But in "odd way" algorithm reduce last swap so we have next situation
Instead of [1, 2, 3] -> [1, 2, 3] We will have [1, 2, 3] -> [3, 2, 1]
And it will also effect on upper levels and so on.
My problem is that I don't understand how can algorithm continue produce correct amount of unique permutations? How can upper calls (it is about recursion) of algorithm correctly choose new unique number?
About last question, when we use algorithm, we use interesting logic that can be found in this publication Here
Please accept my apologies for possible grammatical errors in the text, I am still not very good at communicating in English. If you need any more detailed information, I will be happy to add it to my question.
Here the example from (en.)wikipedia 1,2,3,4,5 ... Original Array
4,1,2,3,5 ... 1st iteration (Permute subset/Rotate subset)
5,1,2,3,4 ... 1st iteration (Swap)
3,5,1,2,4 ... 2nd iteration (Permute subset/Rotate subset)
4,5,1,2,3 ... 2nd iteration (Swap)
2,4,5,1,3 ... 3rd iteration (Permute subset/Rotate subset)
3,4,5,1,2 ... 3rd iteration (Swap)
1,3,4,5,2 ... 4th iteration (Permute subset/Rotate subset)
2,3,4,5,1 ... 4th iteration (Swap)
5,2,3,4,1 ... 5th iteration (Permute subset/Rotate subset)
1,2,3,4,5 ... 5th iteration (Swap) The final state of the array is in the same order as the original
And according to optimization we don't make swap of last 5th iteration, so set doesn't return original state