堆的算法排列生成器

一尘不染

堆的算法排列生成器

algorithm

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

我找到了有关Heap算法的Wikipedia文章（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

在最后一步之前，这似乎还不错，这不是一对交换。

我究竟做错了什么？

阅读 355

2020-07-28

共1个答案

一尘不染

历史序幕

自编写此答案以来，
有关Heap算法的Wikipedia文章已得到纠正，但是您可以在Wikipedia的更改历史记录中看到该问题和答案所引用的版本。

如果打算实现Wikipedia伪代码，则代码（从算法上）没有任何问题。您已经成功实现了所介绍的算法。

但是，提出的算法不是Heap的算法，并且不能保证连续的置换将是单个交换的结果。如您在Wikipedia页面上所见，有时在生成的排列之间会发生多次交换。参见例如线条

CBAD
DBCA

它们之间有三个交换（交换之一是无操作）。

这恰好是代码的输出，这并不奇怪，因为您的代码是所呈现算法的准确实现。

堆算法的正确实现以及错误的根源

有趣的是，伪代码基本上是从Sedgewick的演讲幻灯片（Wikipedia页面上的参考文献3）派生而来的，该幻灯片与前一张幻灯片中的排列列表不对应。我进行了一些摸索，发现了许多不正确的伪代码副本，足以使我怀疑我的分析。

幸运的是，我还查看了Heap的简短论文（Wikipedia页面上的参考文献1），该论文相当清楚。他说的是：（强调添加）

该程序使用相同的通用方法…即，对于n个对象，首先置换第一个（n-1）个对象，然后将第n个单元格的内容与指定单元格的内容互换。在此方法中，如果n为奇数，则此指定的单元始终是第一个单元，但如果n为偶，则从1到
（n-1） 连续编号。

问题在于所提供的递归函数总是在返回之前进行交换（除非N为1）。因此，实际上它确实从1连续交换到 n ，而不是Heap指定的 （n-1）
交换。因此，当（例如）以N == 3调用该函数时，在调用结束时将有两次交换在下一次收益率之前：一次是在N == 2调用结束时进行，另一次是在N ==
2调用结束时进行。 i == N的循环。如果N == 4，将进行三个交换，依此类推。（不过，其中一些将是无人操作的。）

最后一次交换是错误的：算法应该在递归调用之间进行交换，而不是在它们之后进行；它永远不能与交换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页）以匹配Heap的算法。除该行外，其余算法均未更改。介绍了几种变体。

2020-07-28