Python：生成列表的所有有序组合

Question

我正在使用Python 2.7。

我有一个列表，想要获取所有可能的有序组合。

import itertools
stuff = ["a","b","c", "d"]
for L in range(1, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print( ' '.join(subset))

这将会产生以下输出：

a
b
c
d
a b
a c <-- not in correct order
a d <-- not in correct order
b c
b d <-- not in correct order
c d
a b c
a b d <-- not in correct order
a c d <-- not in correct order
b c d
a b c d

但是我希望输出的组合只有与stuff列表中相同顺序的组合。例如，删除a d、b d、a b d和a c d，因为它们与stuff列表["a", "b", "c", "d"]的顺序不正确。

我已经想出了这个替代方法：

import itertools
stuff = ["a","b","c", "d"]
for L in range(1, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        if ' '.join(subset) in ' '.join(stuff): #added line
            print( ' '.join(subset))

给我输出了我想要的结果：

a
b
c
d
a b
b c
c d
a b c
b c d
a b c d

但是在Python中是否有任何内置方法可以做到我想要的？

- amkleist

---

为什么 a d 不是正确的顺序？你所说的“顺序”是什么意思？你只关心原始列表的“片段”吗？为什么 a c 是正确的顺序，而 a d 不是？ 为什么a d不是正确的排序方式？您指的“排序方式”是什么意思？您只对原始列表的“切片”感兴趣吗？为什么a c按正确顺序排列而a d却不是？ - poke

Answer 1

我相信您所寻找的是原始列表的所有可能切片。您所期望的输出翻译成切片就是这样：

a         # slices[0:1]
b         # slices[1:2]
c         # slices[2:3]
d         # slices[3:4]
a b       # slices[0:2]
b c       # slices[1:3]
c d       # slices[2:4]
a b c     # slices[0:3]
b c d     # slices[1:4]
a b c d   # slices[0:4]

所以你应该尝试生成那些索引。如果你仔细观察并排序它们，你会发现这些是0到4之间数字的2个组合，其中第一个数字比另一个小-这正是itertools.combinations 为索引列表执行的操作。所以我们只需要生成这些：

for i, j in itertools.combinations(range(len(stuff) + 1), 2):
    print(stuff[i:j])

这将产生以下输出：

['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['c']
['c', 'd']
['d']

优点在于它能够生成实际的子列表，而不关心它们最初是否只有单个字符。任何类型的内容都可以作为列表中的元素。

如果输出顺序很重要，您可以按照输出列表的大小进行排序以获得所需的结果：

def getCombinations (lst):
    for i, j in itertools.combinations(range(len(lst) + 1), 2):
        yield lst[i:j]

for x in sorted(getCombinations(stuff), key=len):
    print(' '.join(x))

- poke

---

优雅的代码。也许最终结果需要排序，就像示例输出一样。 - WKPlus

@WKPlus 这是个好观点，我加了一种方法来实现。谢谢！ :) - poke

如果您使用 itertools.combinations 而不是 itertools.permutations，则可以省略 if i < j 行。 - WKPlus

@WKPlus 哦，你说得对。我之前测试过，但当时没有 len + 1 这部分，所以它不起作用。我猜后来我没有再次测试它... 再次感谢！ :) - poke

Answer 2

我认为你所说的“按正确顺序”是指连续顺序，在这种情况下，你只需要使用两个指针来迭代stuff:

stuff = ["a","b","c", "d"]
# sort stuff here if it's not sorted

result = []
for i in xrange(len(stuff)):
    for j in xrange(i+1, len(stuff)+1):
        result.append(stuff[i:j])

# sort the result by length, maybe you don't need it
result = sorted(result, key=len)

for r in result:
    print ' '.join(r)

- WKPlus

---

你可以用 key=len 替换 key=lambda x:len(x)。 - TigerhawkT3

@TigerhawkT3 是的，更加优雅。 - WKPlus

你说得对，我认为你的意思是“连续顺序”而非“正确顺序”。谢谢你的回复 :) - amkleist