在一个列表中找到所有可能的有序组合

Question

给定一个有序整数列表：

[1,3,7,8,9]

如何找到原始列表中可以创建的所有子列表，其中保持顺序？使用上面的示例，我正在寻找一种以编程方式生成这些序列的方法：

[[1],[3,7,8,9]]
[[1, 3],[7,8,9]]
[[1, 3, 7],[8,9]]
[[1, 3, 7, 8],[9]]
[[1, 3, 7, 8, 9]]
[[1, 3, 7], [8, 9]]
[[1], [3, 7], [8], [9]]
[[1], [3], [7, 8], [9]]
[[1], [3], [7], [8, 9]]
...

我基本上是在寻找一种方法来生成保持顺序的列表的所有排列。使用以下代码，我可以生成只有2个子列表的所有子列表：

def partition(arr, idx):
    return [arr[:idx], arr[idx:]]

l = [1,3,7,8,9]
for idx in range(1, len(l)):
    groups = partition(l, idx)
    print(groups)

[[1], [3, 7, 8, 9]]
[[1, 3], [7, 8, 9]]
[[1, 3, 7], [8, 9]]
[[1, 3, 7, 8], [9]]

然而，这段代码只将原始列表分成两个部分，并生成仅包含两个子列表的所有可能子列表。如何生成可以从原始列表中创建的所有可能子列表，其中保持顺序？

- turtle

Answer 1

如何呢：

import itertools

def subsets(seq):
    for mask in itertools.product([False, True], repeat=len(seq)):
        yield [item for x, item in zip(mask, seq) if x]

def ordered_groups(seq):
    for indices in subsets(range(1, len(seq))):
        indices = [0] + indices + [len(seq)]
        yield [seq[a:b] for a,b in zip(indices, indices[1:])]

for group in ordered_groups([1,3,7,8,9]):
    print group

结果：

[[1, 3, 7, 8, 9]]
[[1, 3, 7, 8], [9]]
[[1, 3, 7], [8, 9]]
[[1, 3, 7], [8], [9]]
[[1, 3], [7, 8, 9]]
[[1, 3], [7, 8], [9]]
[[1, 3], [7], [8, 9]]
[[1, 3], [7], [8], [9]]
[[1], [3, 7, 8, 9]]
[[1], [3, 7, 8], [9]]
[[1], [3, 7], [8, 9]]
[[1], [3, 7], [8], [9]]
[[1], [3], [7, 8, 9]]
[[1], [3], [7, 8], [9]]
[[1], [3], [7], [8, 9]]
[[1], [3], [7], [8], [9]]

- Kevin

---

看起来你正在重新发明“子集”的轮子。我相信使用itertools.combinations可以更容易地完成同样的事情。 - Dunes

我想你可以将subsets定义为for i in range(len(seq)+1): for x in itertools.combinations(seq, i): yield list(x)。不过我不确定是否只用一个for循环就能实现。 - Kevin

[item for x, item in zip(mask, seq) if x] -> list(itertools.compress(seq, mask)) - Navith

哦，不错，我之前一直忽略了“压缩”这个功能。今天我学到了。 - Kevin

这是我唯一找到它有用的时候。 - Navith