14

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

我找到了有关 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

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

我究竟做错了什么？

4

3 回答 3

35

历史序幕

自编写此答案以来，有关 Heap 算法的Wikipedia 文章已得到更正，但您可以在Wikipedia's change history中查看问题和答案所引用的版本。

如果您打算实现 Wikipedia 伪代码，那么您的代码（算法上）没有任何问题。您已经成功实现了提出的算法。

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

CBAD
DBCA

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

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

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

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

幸运的是，我还查看了 Heap 的简短论文（Wikipedia 页面上的参考文献 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，将有 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 页）以匹配 Heap 的算法。除了那条线，算法的其余部分没有改变。提出了几种变体。

于 2015-03-14T02:58:33.623 回答
-1

我刚刚将维基百科关于堆算法的文章中的非递归伪代码解释为 Python：

A = ['a', 'b', 'c', 'd', 'e', 'f', 'g'] #the initial list to permute
n = len(A) #length of A
print(A) # output the first permutation (i.e. the original list A itself)
number_of_permutations = 1 #a variable to count a number of permutations produced by the script
total = [] #a list contaning all generated permutations
t = tuple(A) #tuple containing each permutation
total.append(t) #adding each permutation to total
c = [0] * n #c is the list used to track swapping of positions in each iteration of the Heap`s alrorythm.
i = 0 #index of positions in A and c. Serves as a pointer for swapping of positions in A.

while i < n:
    if c[i] < i: # test whether ith position was swapped more than i - 1 times
        if i % 2 == 0: #swapping the poitions in A
            A[0], A[i] = A[i], A[0]
        else:
            A[c[i]], A[i] = A[i], A[c[i]]
        print(A) #output of each permutation
        t = tuple(A) #convert each permutations into unmutable object (tuple)
        total.append(t) # appending each permutation as tuple in the list of all generated permutations
        number_of_permutations += 1 #increment number of performed permutations
        c[i] += 1 # incrementing c[i] is used to indicate that ith position was swapped
        i = 0 #returns the pointer to the 0th position (imitates recursion)
    else:
        c[i] = 0 #when ith position in A was swapped i - 1 times c[i] resets to zero
        i += 1 #pointer moves to the next position

print('Number of permutations generated by the script = ', number_of_permutations)

#Examining the correctness of permutions. Total number of permutations should be n! and there should not be any repeates
def factorial(n):
    """ Factorial function"""
    result = 1
    for number in range(1, n + 1):
        result *= number
    return result

print('Theoretical number of permutations (calculated as n!) = ', factorial(n))

for seq in total: #testing repeates
    count = total.count(seq)
    if count > 1:
        x = False
    else:
        x = True
print('The script does not generates repeats' if x == True else 'The script generates repeats')

我还在那里介绍了一个测试结果的正确性（没有重复的所有排列的数量应该等于 n！）。看起来脚本运行良好。我仍然不完全理解它是如何工作的。但是我根据自己的理解在代码中添加了注释。

于 2021-11-07T19:52:32.500 回答
-4

获取列表排列的最简单方法是 itertools 模块中的 permutations 函数。所以，如果算法没有约束力，我会这样做：

from itertools import permutations

a = [1,2,3,4]
for item in permutations(a):
    print item
于 2015-03-14T06:47:00.050 回答