在Python中生成（不完全）生成集的算法

Question

这段内容是对之前一个问题的延续：

生成覆盖集合的算法

给定这个输入：[1,2,3,4]

我想在Python中生成这个集合的集合：

[1] [2] [3] [4]
[1] [2] [3,4]
[1] [2, 3, 4]
[1] [2,3] [4]
[1,2] [3] [4]
[1,2] [3,4]
[1,2,3] [4]
[1,2,3,4]

所以和之前的问题不同，这里保留了列表的顺序。

理想情况下，这段代码应该能处理列表中的n个项目。

非常感谢！

编辑2：如果原始输入是一个字符串而不是列表（字符串中的每个单词变成列表中的一个项目），请问我该怎么做呢？谢谢！

编辑：添加了[1] [2, 3, 4] 抱歉之前的错误

Answer 1

import itertools
a = [1, 2, 3, 4]
n = len(a)
for num_splits in range(n):
    for splits in itertools.combinations(range(1, n), num_splits):
        splices = zip([0] + list(splits), list(splits) + [n])
        print([a[i:j] for i, j in splices])

打印

[[1, 2, 3, 4]]
[[1], [2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 2, 3], [4]]
[[1], [2], [3, 4]]
[[1], [2, 3], [4]]
[[1, 2], [3], [4]]
[[1], [2], [3], [4]]

Answer 2

调整了来自 Python: 显示列表的所有可能分组 的一个解决方案：

from itertools import combinations

def cut(lst, indexes):
    last = 0
    for i in indexes:
        yield lst[last:i]
        last = i
    yield lst[last:]

def generate(lst, n):
    for indexes in combinations(list(range(1,len(lst))), n - 1):
        yield list(cut(lst, indexes))

data = [1,2,3,4]

for i in range(1, len(data)+1):  # the only difference is here
    for g in generate(data, i):
        print(g)

"""
[[1, 2, 3, 4]]
[[1], [2, 3, 4]]
[[1, 2], [3, 4]]
[[1, 2, 3], [4]]
[[1], [2], [3, 4]]
[[1], [2, 3], [4]]
[[1, 2], [3], [4]]
[[1], [2], [3], [4]]
"""

Answer 3

你可能会喜欢一种递归的解决方案：

def span(lst):
  yield [lst]
  for i in range(1, len(lst)):
    for x in span(lst[i:]):
      yield [lst[:i]] + x

解释

我们在这里利用递归来把问题拆解。具体方法如下：

对于每一个列表，整个列表都是一个有效的组合：[1,2,3,4] => [[1,2,3,4]]。

对于每个长度大于 1 的列表，我们可以把第一个元素当作一组，然后对剩下的列表应用同样的算法，得到所有的组合结果：

[1,2,3] => 
  [[1]] + [[2], [3]]  # => [[1], [2], [3]]
  [[1]] + [[2,3]]     # => [[1], [2,3]]

对于每个长度大于 2 的列表，我们也可以把前两个元素当作一组，然后对剩下的列表应用同样的算法，组合结果：

[1,2,3,4,5] =>
  [[1,2]] + [[3], [4], [5]]  # => [[1,2], [3], [4], [5]]
  [[1,2]] + [[3,4], [5]]     # => [[1,2], [3,4], [5]]
  [[1,2]] + [[3], [4,5]]     # => [[1,2], [3], [4,5]]
  [[1,2]] + [[3,4,5]]        # => [[1,2], [3,4,5]]

我们可以看到右边的所有可能组合确实是剩下列表 [3,4,5] 的所有可能分组。

对于每个长度更长的列表……等等。因此，最终的算法如下：

1. 返回整个列表（它总是一个有效的组合，见上文）
2. 对于列表的每一种可能分割，返回左边部分与右边部分所有可能组合的结果。

yield 是 Python 中的一个特殊关键字，它使得函数成为一个 生成器，这意味着它返回一个可迭代的对象，可以用来列举所有找到的结果。你可以使用 list 构造函数把结果转换成列表：list(span([1,2,3,4]))。