我正试图找到一种算法，使我能够创建列表元素的所有排列/组合，包括当省略每个排列/组合时发生的排列/组合。
例如，包含的列表
[a, b, c]
应该产生标准排列
[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, b, a], [c, a, b]
还包括当列表条目之一被省略时产生的这些结果
[a, b], [a, c], [b, a], [b, c], [c, a], [c, b]
和
[a], [b], [c]
有人知道这里的最佳方法吗？不幸的是，Heap的算法只生成标准排列，我还没有找到任何其他算法来提供我需要的整个排列谱。
下面是Heap算法在Python中的一个简单实现，它是作为生成器编写的。它可能不是你习惯的演示，因为它使用了一个经过中期测试的循环，这是Robert Sedgewick最初演示的方式，但它有完全相同的步骤序列。(不幸的是，Python没有经过中期测试的循环结构，所以这个版本一开始也有一个无用的测试。(
def heap_perm(it):
def helper(n):
if n == 0:
yield A[:]
else:
for i in range(n):
yield from helper(n-1)
if i < n - 1:
if n % 2:
A[0], A[n-1] = A[n-1], A[0]
else:
A[i], A[n-1] = A[n-1], A[i]
A = list(it)
yield from helper(len(A))
该算法生成的排列顺序的一个重要方面是，具有特定后缀的所有排列都是连续输出的，而与后缀的长度无关。因此，如果我们也想要所有的后缀，我们只需要在第一次遇到后缀时产生它，就在递归之前。如果你把这两个函数放在一起，你会发现它们有多么相似。
def heap_subset_perm(it):
def helper(n):
for i in range(n):
yield A[n-1:]
yield from helper(n-1)
if i < n - 1:
if n % 2:
A[0], A[n-1] = A[n-1], A[0]
else:
A[i], A[n-1] = A[n-1], A[i]
A = list(it)
yield from helper(len(A))
在示例运行中，我对输出进行了右对齐，以便后缀属性更加可见：
>>> for p in heap_subset_perm("abcd"):
... print(f"{str(p):>20}")
...
['d']
['c', 'd']
['b', 'c', 'd']
['a', 'b', 'c', 'd']
['a', 'c', 'd']
['b', 'a', 'c', 'd']
['b', 'd']
['a', 'b', 'd']
['c', 'a', 'b', 'd']
['c', 'b', 'd']
['a', 'c', 'b', 'd']
['a', 'd']
['c', 'a', 'd']
['b', 'c', 'a', 'd']
['b', 'a', 'd']
['c', 'b', 'a', 'd']
['c']
['a', 'c']
['b', 'a', 'c']
['d', 'b', 'a', 'c']
['d', 'a', 'c']
['b', 'd', 'a', 'c']
['b', 'c']
['d', 'b', 'c']
['a', 'd', 'b', 'c']
['a', 'b', 'c']
['d', 'a', 'b', 'c']
['d', 'c']
['a', 'd', 'c']
['b', 'a', 'd', 'c']
['b', 'd', 'c']
['a', 'b', 'd', 'c']
['b']
['d', 'b']
['c', 'd', 'b']
['a', 'c', 'd', 'b']
['a', 'd', 'b']
['c', 'a', 'd', 'b']
['c', 'b']
['a', 'c', 'b']
['d', 'a', 'c', 'b']
['d', 'c', 'b']
['a', 'd', 'c', 'b']
['a', 'b']
['d', 'a', 'b']
['c', 'd', 'a', 'b']
['c', 'a', 'b']
['d', 'c', 'a', 'b']
['a']
['b', 'a']
['c', 'b', 'a']
['d', 'c', 'b', 'a']
['d', 'b', 'a']
['c', 'd', 'b', 'a']
['c', 'a']
['d', 'c', 'a']
['b', 'd', 'c', 'a']
['b', 'c', 'a']
['d', 'b', 'c', 'a']
['d', 'a']
['b', 'd', 'a']
['c', 'b', 'd', 'a']
['c', 'd', 'a']
['b', 'c', 'd', 'a']
您可以对按照前缀顺序生成排列的排列生成器做同样的事情，例如在itertools中实现的字典顺序生成器。
我通过递归调用Heap的算法来解决这个问题，每次递归都包含一个循环，每次迭代分别删除一个元素。这会缩小列表，并在每次递归中迭代删除每个条目一次，然后对剩余条目进行排列。