Heap的算法置换生成器
Heap's algorithm permutation generator
我需要迭代整数元组的排列。顺序必须通过在每一步交换一对元素来生成。
我找到了关于 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
这似乎很好，直到最后一步，这不是一对交换。
我做错了什么？
历史序幕
Wikipedia article on Heap's algorithm has been corrected, defaced and corrected again several times since this answer was written. The version referred to by the question and original answer was incorrect; you can see it in Wikipedia's change history。当前版本可能正确也可能不正确；在进行此次编辑时（2022 年 3 月），该页面包含正确和错误的版本。
如果您打算实施维基百科伪代码，那么您的代码（从算法上来说）没有任何问题。您已成功实现所提供的算法。
然而，所提供的算法不是Heap 的算法，它不保证连续的排列将是单次交换的结果。正如您在维基百科页面中看到的那样，有时在生成的排列之间会发生多次交换。参见例如行
CBAD
DBCA
它们之间有 3 个交换（其中一个交换是空操作）。
这正是您代码的输出，这并不奇怪，因为您的代码是所提供算法的准确实现。
Heap算法的正确实现，以及错误的来源
有趣的是，伪代码基本上源自 Sedgewick 在 2002 年发表的演讲中的幻灯片（维基百科页面上的参考文献 3，也 currently available on Sedgewick's home page）。不正确的伪代码在幻灯片 13 上，它显然是错误的，因为它与前一张幻灯片上显示算法工作的有用图形不对应。我做了一些调查，发现了这个不正确的伪代码的许多副本，足以开始怀疑我的分析。
还好我也看了Heap的short paper（维基百科页面参考文献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，而不是 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
注： 上面的函数是为了模仿原题中的同名函数而写的，它执行排列就地。就地进行排列可以节省复制返回的每个排列的成本，使完整生成 O(n!)（或每个排列生成的 O(1)）而不是 O(n·n!)（或每个排列的 O(n)产生）。如果您要立即处理每个排列，那很好，但如果您的计划是保留它们，那会很混乱，因为对生成器的下一次调用将修改先前生成的列表。在这种情况下，您可能希望将函数调用为
for perm in map(tuple, heap_perm(n, A)):
# Now each perm is independent of the previous one
或者将它们全部收集到一个巨大的列表中（不推荐！！；列表很大），例如 perms = list(map(tuple, heap_perm(n, A)))。
Sedgewick 的原始论文
当我找到 Sedgewick 1977 年的论文 [见注释 1] 时，我很高兴地发现他在那里提出的算法是正确的。但是，它使用循环控制结构（归功于 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 页）以匹配堆的算法。除了那一行，算法的其余部分没有改变。提供了几种变体。
备注：
- 当我写这个答案时，论文中唯一的 public link 是维基百科页面参考中的付费墙 URL。现在可以在 Sedgewick's home page.
上使用
获取列表排列的最简单方法是 itertools 模块中的排列函数。所以，如果算法没有约束力，我会这样做：
from itertools import permutations
a = [1,2,3,4]
for item in permutations(a):
print item
我刚刚解释 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！）。看起来脚本运行良好。我仍然不完全理解它是如何工作的。但是我根据自己的理解在代码中添加了注释。
我需要迭代整数元组的排列。顺序必须通过在每一步交换一对元素来生成。
我找到了关于 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
这似乎很好，直到最后一步，这不是一对交换。
我做错了什么？
历史序幕
Wikipedia article on Heap's algorithm has been corrected, defaced and corrected again several times since this answer was written. The version referred to by the question and original answer was incorrect; you can see it in Wikipedia's change history。当前版本可能正确也可能不正确；在进行此次编辑时（2022 年 3 月），该页面包含正确和错误的版本。
如果您打算实施维基百科伪代码，那么您的代码（从算法上来说）没有任何问题。您已成功实现所提供的算法。
然而，所提供的算法不是Heap 的算法，它不保证连续的排列将是单次交换的结果。正如您在维基百科页面中看到的那样，有时在生成的排列之间会发生多次交换。参见例如行
CBAD
DBCA
它们之间有 3 个交换（其中一个交换是空操作）。
这正是您代码的输出，这并不奇怪，因为您的代码是所提供算法的准确实现。
Heap算法的正确实现，以及错误的来源
有趣的是，伪代码基本上源自 Sedgewick 在 2002 年发表的演讲中的幻灯片（维基百科页面上的参考文献 3，也 currently available on Sedgewick's home page）。不正确的伪代码在幻灯片 13 上，它显然是错误的，因为它与前一张幻灯片上显示算法工作的有用图形不对应。我做了一些调查，发现了这个不正确的伪代码的许多副本，足以开始怀疑我的分析。
还好我也看了Heap的short paper（维基百科页面参考文献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，而不是 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
注： 上面的函数是为了模仿原题中的同名函数而写的，它执行排列就地。就地进行排列可以节省复制返回的每个排列的成本，使完整生成 O(n!)（或每个排列生成的 O(1)）而不是 O(n·n!)（或每个排列的 O(n)产生）。如果您要立即处理每个排列，那很好，但如果您的计划是保留它们，那会很混乱，因为对生成器的下一次调用将修改先前生成的列表。在这种情况下，您可能希望将函数调用为
for perm in map(tuple, heap_perm(n, A)):
# Now each perm is independent of the previous one
或者将它们全部收集到一个巨大的列表中（不推荐！！；列表很大），例如 perms = list(map(tuple, heap_perm(n, A)))。
Sedgewick 的原始论文
当我找到 Sedgewick 1977 年的论文 [见注释 1] 时，我很高兴地发现他在那里提出的算法是正确的。但是，它使用循环控制结构（归功于 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 页）以匹配堆的算法。除了那一行，算法的其余部分没有改变。提供了几种变体。
备注：
- 当我写这个答案时，论文中唯一的 public link 是维基百科页面参考中的付费墙 URL。现在可以在 Sedgewick's home page. 上使用
获取列表排列的最简单方法是 itertools 模块中的排列函数。所以，如果算法没有约束力，我会这样做：
from itertools import permutations
a = [1,2,3,4]
for item in permutations(a):
print item
我刚刚解释 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！）。看起来脚本运行良好。我仍然不完全理解它是如何工作的。但是我根据自己的理解在代码中添加了注释。