python - 堆的算法置换生成器

Question

我需要迭代整数元组的排列。必须通过在每一步交换一对元素来生成顺序。

我找到了堆算法的维基百科文章( http://en.wikipedia.org/wiki/Heap%27s_algorithm )，应该这样做。伪代码是:

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 中为此编写一个生成器:

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] 的输入):

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

这似乎很好，直到最后一步，这不是一对交换。

我究竟做错了什么？

Answer 1

历史序幕

Wikipedia article on Heap's algorithm自从撰写此答案以来已更正，但您可以在 Wikipedia's change history 中看到问题和答案中提到的版本.

如果您打算实现维基百科伪代码，那么您的代码(在算法上)没有问题。您已成功实现了所提供的算法。

但是，所提供的算法不是 Heap 的算法，并且它不保证连续排列将是单个交换的结果。正如您在维基百科页面中看到的那样，有时生成的排列之间会发生多次交换。参见例如线条

CBAD
DBCA

它们之间有三个交换(交换之一是空操作)。

这正是您代码的输出，这并不奇怪，因为您的代码是所提供算法的准确实现。

Heap算法的正确实现，以及错误的来源

有趣的是，伪代码基本上来自 Sedgewick 的演讲幻灯片(维基百科页面上的引用文献 3)，它与前一张幻灯片上的排列列表不对应。我做了一些调查，发现了很多这个错误伪代码的副本，足以让我开始怀疑我的分析。

幸运的是，我还查看了 Heap 的简短论文(维基百科页面上的引用文献 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).

问题是所呈现的递归函数总是在返回之前进行交换(除非 N 为 1)。所以它实际上从 1 到 连续交换 ，不是 (n−1) 正如堆指定的那样。因此，当(例如)以 N==3 调用该函数时，在下一次 yield 之前的调用结束时将有两次交换:一次来自 N==2 调用的结束，另一次来自i==N 的循环。如果 N==4，则将有 3 次交换，依此类推。 (不过，其中一些将是无操作的。)

最后一次交换不正确:算法应该在递归调用之间进行交换，而不是在它们之后；它永远不应该与 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

塞奇威克的原始论文

我找到了 Sedgewick 1977 年论文的副本(不幸的是，维基百科给出的链接是付费的)，并且很高兴地发现他在那里提出的算法是正确的。然而，它使用了一个循环控制结构(归功于 Donald Knuth)，这对于 Python 或 C 程序员来说可能看起来很陌生:一个中间循环测试:

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 页，其中 Sedgewick 解释了如何修改算法 1 的原始版本(第 140 页)以匹配堆的算法。除了那条线之外，算法的其余部分没有变化。介绍了几种变体。