堆的算法置换生成器

Question

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

我找到了用于Heap算法的维基百科文章(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

历史序幕

关于Heap算法的维基百科文章已被更正,因为这个答案是写的,但你可以看到维基百科的变更历史中问答所引用的版本.

如果您打算实现Wikipedia伪代码,那么您的代码(算法上)没有任何问题.您已成功实现了所提出的算法.

然而,所提出的算法不是Heap的算法,并且它不能保证连续的排列将是单个交换的结果.正如您在维基百科页面中看到的,有时在生成的排列之间发生多次交换.例如,参见线条

CBAD
DBCA

它们之间有三次交换(其中一个交换是无操作).

这正是代码的输出,这并不奇怪,因为您的代码是所提算法的精确实现.

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

有趣的是,伪代码基本上来自Sedgewick的谈话幻灯片(维基百科页面上的参考文献3),这与前一张幻灯片上的排列列表不对应.我做了一些调查,发现了这个不正确的伪代码的许多副本,足以开始怀疑我的分析.

幸运的是,我还查看了Heap的简短论文(维基百科页面上的参考文献1),这是相当清楚的.他说的是:(重点补充)

程序使用相同的通用方法...即对于n个对象,首先置换第一个(n-1)个对象,然后将第n个单元格的内容与指定单元格的内容进行交换.在此方法中,如果n为奇数,则此指定单元始终是第一个单元,但如果n为偶数,则从1到(n-1)连续编号.

问题是所呈现的递归函数在返回之前总是进行交换(除非N为1).所以它实际上是从1到n连续交换,而不是Heap指定的(n-1).因此,当(例如)用N == 3调用函数时,在下一个yield之前调用结束时将有两个交换:一个来自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的原始版本(第134页)以匹配Heap的算法.除了该行,算法的其余部分保持不变.提出了几种变体.