堆算法排列生成 [英] Heap's algorithm permutation generator
问题描述
我需要遍历整数元组的排列。的顺序必须通过交换的一对元件中的每一个步骤中生成
I need to iterate over permutations of a tuple of integers. The order has to be generated by swapping a pair of elements at each step.
我发现维基百科的文章（ http://en.wikipedia.org/wiki/Heap% 27s_algorithm ），用于堆的算法，这是应该做到这一点。伪code是：
I found the Wikipedia article (http://en.wikipedia.org/wiki/Heap%27s_algorithm) for Heap's algorithm, which is supposed to do this. The pseudocode is:
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])
我试着写了这Python中的发电机：
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
这将产生按以下顺序排列（用于输入[0,1,2,3]）：
This produces permutations in the following order (for input of [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 fine until that last step, which isn't a swap of one pair.
我是什么做错了吗？
推荐答案
的维基百科的文章上堆算法已得到纠正，因为这个答案是编写的，但你可以看到的问题中提到的版本和回答的维基百科的变化记录。的
Historical prologue
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.
这没有什么不对您code（算法），如果你打算实施维基百科的伪code。您已成功实现的算法presented。
There's nothing wrong with your code (algorithmically), if you intended to implement the Wikipedia pseudocode. You have successfully implemented the algorithm presented.
然而，该算法presented不是堆的算法，它不能保证连续置换将是一个单一交换的结果。正如你可以在维基百科页面看到，有些时候，多掉期产生的排列之间产生。例如见行
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. As you can see in the Wikipedia page, there are times when multiple swaps occur between generated permutations. See for example the lines
CBAD
DBCA
这让他们之间有三个互换（掉期之一是无操作）。
which have three swaps between them (one of the swaps is a no-op).
这是precisely从code，这并不奇怪，因为你的code是一个准确的实现算法presented输出。
This is precisely the output from your code, which is not surprising since your code is an accurate implementation of the algorithm presented.
有趣的是，伪code为基本上来自于塞奇威克的谈话载玻片（参考3维基百科页上），其不对应于上立即preceding滑动排列的列表。我身边做了一些侦探，发现这种不正确的伪code多份，足以开始怀疑自己的分析。
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. I did some sleuthing around, and found many copies of this incorrect pseudo-code, enough to start to doubt my analysis.
幸运的是，我又看了看堆的短文（参考文献1维基百科的页面上），这是相当清楚的。他说的是：（强调）
Fortunately, I also looked at Heap's short paper (reference 1 on the Wikipedia page), which is reasonably clear. What he says is: (emphasis added)
本方案采用相同的一般方法和hellip;即对于n个对象，第一重排的第一（N-1）对象，然后交换第n个单元的内容与那些特定细胞。在这种方法中，这个特殊的细胞永远是第一个单元格，如果n为奇数，但如果n为偶数，这是连续编号从1到。（N减1）
The program uses the same general method … i.e. 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. 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).
的问题是，递归函数为$ P $总是psented做了交换返回之前（除非N为1）。因此，它实际上做掉期连续从1到， N 不是（N减1）作为堆规定。因此，当（例如）函数被调用用N == 3，将有两个交换在呼叫的下屈服之前结束：1从N == 2呼叫的结束，并从其他的一个与我在循环==ñ。如果如果N == 4，将有三个互换，并依此类推。 （其中一些将是空操作，但。）
The problem is that the recursive function as presented always does a swap before returning (unless N is 1). So it actually does swaps consecutively from 1 to n, not (n−1) as Heap specifies. 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. If if N==4, there will be three swaps, and so on. (Some of these will be no-ops, though.)
最后一笔掉期是不正确的：该算法应该做掉期的在的递归调用，不要出去;它不应该与交换I ==ñ。
The last swap is incorrect: The algorithm should do swaps between recursive calls, not after them; it should never swap with i==N.
所以，这应该工作：
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
塞奇威克的原始文件
我发现了塞奇威克的1977年文件的副本，（维基百科给出的链接paywalled，可悲的是），并很高兴地发现，自己presents算法有正确的。但是，它使用一个循环控制结构（记为高德纳），这似乎是陌生的Python或C程序员：中间回路测试：
Sedgewick's original paper
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. However, it uses a looping control structure (credited to Donald Knuth) which might seem foreign to Python or C programmers: a mid-loop 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;
注意：的的互换额度是从141页，塞奇威克介绍如何修改算法1的原始版本（第140页），以适应堆的算法。除此之外线，算法的其余部分保持不变。有几个变种presented。
Note: The swap line is taken from page 141, where Sedgewick explains how to modify the original version of Algorithm 1 (on page 140) to match Heap's algorithm. Aside from that line, the rest of the Algorithm is unchanged. Several variants are presented.
这篇关于堆算法排列生成的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
