Proof of correctness of some optimization of Heap's algorithm for producing permutations

Question

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[0], 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[0], 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

• Inuyasha Yagami: I can not access the publication link. Could you please check that. :) Give a reference probably.
• Forelyl: @InuyashaYagami Sure, sorry for that. academic.oup.com/comjnl/article/6/3/293/360213?login=false

Answer 1

Your this claim: "When algorithm uses "even way" the optimization doesn't change logic and result" is incorrect.

Since the "even way" is dependent on the "odd way" (due to recursive dependency), the optimization does change the result.

For example, consider the following example when optimized algorithm is used for even sized array:

$[1 ,円 2 ,円 3 ,円 4]$: Original Array

$[3 ,円 2 ,円 1 ,円 4]$: First iteration (Permute subset/Rotate subset)

$[4 ,円 2 ,円 1 ,円 3]$: First iteration (Swap)

$[1 ,円 2 ,円 4 ,円 3]$: Second iteration (Permute subset/Rotate subset)

$[1 ,円 3 ,円 4 ,円 2]$: Second iteration (Swap)

$[4 ,円 3 ,円 1 ,円 2]$: Third iteration (Permute subset/Rotate subset)

$[4 ,円 3 ,円 2 ,円 1]$: Third iteration (Swap)

$[2 ,円 3 ,円 4 ,円 1]$: Fourth iteration (Permute subset/Rotate subset)

Note that you did not obtain $[1 ,円 2 ,円 3 ,円 4]$ (unaltered array) but you obtained an altered array, i.e., $[2 ,円 3 ,円 4 ,円 1]$.