Heap Algorithm Permutation Generator

Question

I need to iterate over permutations of tuples of integers. The order should be generated by replacing a pair of elements at each step.

I found a Wikipedia article ( http://en.wikipedia.org/wiki/Heap%27s_algorithm ) for the Heap algorithm that should do this. Pseudocode:

procedure generate(n : integer, A : array of any): if n = 1 then output(A) else for i := 1; i ≤ n; i += 1 do generate(n - 1, A) if n is odd then j ← 1 else j ← i swap(A[j], A[n]) 

I tried to write a generator for this in python:

 def heap_perm(A): n = len(A) Alist = [el for el in A] for hp in _heap_perm_(n, Alist): yield hp def _heap_perm_(n, A): if n == 1: yield A else: for i in range(1,n+1): for hp in _heap_perm_(n-1, A): yield hp if (n % 2) == 1: j = 1 else: j = i swap = A[j-1] A[j-1] = A[n-1] A[n-1] = swap 

This creates permutations in the following order (for input [0,1,2,3]):

 0,1,2,3 1,0,2,3 2,0,1,3 0,2,1,3 1,2,0,3 2,1,0,3 3,1,2,0 and so on 

This seems perfect until the last step, which is not a swap of one pair.

What am I doing wrong?

Answer 1

Historical prologue

The Wikipedia article on the heap algorithm has been fixed since this answer was written, but you can see the version referenced by the question and answer in the Change History on Wikipedia .

There is nothing wrong with your code (algorithmically) if you intended to implement the Wikipedia pseudocode. You have successfully implemented the presented algorithm.

However, the presented algorithm is not a heap algorithm, and it does not guarantee that subsequent permutations will be the result of a single exchange. As you can see on the Wikipedia page, there are times when several swaps occur between generated permutations. See for example the lines

 CBAD DBCA 

which have three swaps between them (one of the swaps is no-op).

This is just the result of your code, which is not surprising, since your code is an exact implementation of the presented algorithm.

Correct heap algorithm implementation and error source

Interestingly, the pseudo-code is mainly derived from Sedgewick slide slides (link 3 on the Wikipedia page), which does not match the permutation list on the previous slide. I got a little worried and found many copies of this incorrect pseudo-code, enough to doubt my analysis.

Fortunately, I also looked at Kuchi's short newspaper (link 1 on the Wikipedia page), which is clear enough. He says the following: (italics)

The program uses the same general & hellip; that is, for n objects, first transfer the first (n-1) objects, and then replace the contents of the nth cell with the cells of the specified cell. In this method, this indicated cell is always the first cell if n is odd, but if n is even, it is sequentially numbered from 1 to (n minus 1) .

The problem is that the recursive function represented always executes the swap before returning (if N is 1). Thus, it does swap sequentially from 1 to n , rather than (n & minus; 1) , as indicated on the heap. Therefore, when (for example) a function is called with N == 3, at the end of the call there will be two swaps until the next exit: one from the end of the call N == 2, and the other from the loop with i == N. If if N == 4, there will be three swaps, etc. (Some of them will be non-ops.)

The last swap is incorrect: the algorithm should make swaps between recursive calls, and not after them; it should never change with i==N

So this should work:

 def _heap_perm_(n, A): if n == 1: yield A else: for i in range(n-1): for hp in _heap_perm_(n-1, A): yield hp j = 0 if (n % 2) == 1 else i A[j],A[n-1] = A[n-1],A[j] for hp in _heap_perm_(n-1, A): yield hp 

Original Sedgewick Paper

I found a copy of Sejuik's 1977 article (the link made by wikipedia, paid, sadly), and was glad to find that the algorithm he presents there is correct. However, it uses a loop control structure (attributed to Donald Knuth), which may seem like a stranger to Python or C programmers: a mid-cycle test:

 Algorithm 1: procedure permutations (N); begin c:=1; loop: if N>2 then permutations(N-1) endif; while c<N: # Sedgewick uses :=: as the swap operator # Also see note below if N odd then P[N]:=:P[1] else P[N]:=:P[c] endif; c:=c+l repeat end; 

Note. The swap line is taken from page 141, where Sedgewick explains how to change the original version of Algorithm 1 (on page 140) to match the heap algorithm. Besides this line, the rest of the Algorithm does not change. Several options are presented.

Answer 2

The easiest way to get permutations in a list is with the permutations function in the itertools module. So, if the algorithm is optional, I would go with this:

 from itertools import permutations a = [1,2,3,4] for item in permutations(a): print item 

Answer 3

Just want to share the link for the correct pseudocode: http://desple.com/post/118425815657/permutations-with-heaps-algorithm-in-javascript

it differs from the pseudocode on the Wikipedia page:

 generate (n, arr) if n = 1 output arr else for i = 0; i < n; i += 1 generate (n - 1, arr) if n is even swap(arr[i], arr[n - 1]) else swap(arr[0], arr[n - 1]) 

There is an additional generate (n - 1, arr) operator on the Wikipedia page after replacement, which leads to redundant results.