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

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

您可能还会喜欢递归解决方案：

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]]

。

对于每个大于size的列表

1

，我们可以将第一项作为一个组，然后对其余列表应用相同的算法以获取所有组合结果：

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

对于每个大于size的列表

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中的特殊关键字，它使函数成为 generator
，这意味着它返回一个可迭代的对象，该对象可用于枚举找到的所有结果。您可以将结果为使用列表

list

构造函数：

list(span([1,2,3,4]))

。