I found a copy of Sedgewick's 1977 paper, (the link given by wikipedia is paywalled, sadly), and was delighted to find that the algorithm he presents there is correct. So this should work: def _heap_perm_(n, A): The last swap is incorrect: The algorithm should do swaps between recursive calls, not after them it should never swap with i=N. If if N=4, there will be three swaps, and so on. Consequently, when (for example) the function is called with N=3, there will be two swaps at the end of the call before the next yield: one from the end of the N=2 call, and the other one from the loop with i=N. So it actually does swaps consecutively from 1 to n, not (n−1) as Heap specifies. The problem is that the recursive function as presented always does a swap before returning (unless N is 1). In this method this specified cell is always the first cell if n is odd, but if n is even, it is numbered consecutively from 1 to (n−1). for n objects, first permute the first (n-1) objects and then interchange the contents of the nth cell with those of a specified cell. The program uses the same general method … i.e. I did some sleuthing around, and found many copies of this incorrect pseudo-code, enough to start to doubt my analysis.įortunately, I also looked at Heap's short paper (reference 1 on the Wikipedia page), which is reasonably clear. Interestingly, the pseudocode is basically derived from Sedgewick's talk slides (reference 3 on the Wikipedia page), which does not correspond to the list of permutations on the immediately preceding slide. The correct implementation of Heap's algorithm, and the source of the error
#PERMUTATION GENERATOR ALGORITHM CODE#
This is precisely the output from your code, which is not surprising since your code is an accurate implementation of the algorithm presented. Which have three swaps between them (one of the swaps is a no-op). As you can see in the Wikipedia page, there are times when multiple swaps occur between generated permutations. However, the algorithm presented is not Heap's algorithm, and it does not guarantee that successive permutations will be the result of a single interchange.
You have successfully implemented the algorithm presented.
There's nothing wrong with your code (algorithmically), if you intended to implement the Wikipedia pseudocode. The Wikipedia article on Heap's algorithm has been corrected since this answer was written but you can see the version referred to by the question and answer in Wikipedia's change history. This seems fine until that last step, which isn't a swap of one pair. This produces permutations in the following order (for input of ): 0,1,2,3 I tried to write a generator for this in python: def heap_perm(A): The pseudocode is: procedure generate(n : integer, A : array of any): I found the Wikipedia article ( ) for Heap's algorithm, which is supposed to do this. The order has to be generated by swapping a pair of elements at each step. I need to iterate over permutations of a tuple of integers.
0 kommentar(er)
