如何在Python中运行子集与条件的组合

Question

我有一个列表列表，每个列表元素 len 均按升序排列。例如，

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

。

我想获得他们的所有子集，例如

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

...所以我尝试了

from itertools import chain, combinations
cha=[]
end = int(len([[1], [1,2], [2,3], [3,4], [1,2,3], [1,3,4]]) // 3) + 1
for i in range(1, end):
    cha.extend(list(combinations([[1], [1,2], [2,3], [3,4], [1,2,3], [1,3,4]],i)))
print(cha)

问题是我的列表有 72 个元素，它将是 72C1 + 72C2 + ... + 72C25。性能很差，到了72C6就停止了。

但是，有一些条件可以跳过某些组合，即子集中的元素总数超过 6 时。如

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

。由于我的列表是len顺序的，当有

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

时，可以跳过计算

([1], [1, 2], [2, 3], [1,2,3])

和

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

，直接结束。我认为可以减少大量计算并且性能可以更好。但我怎样才能实现这个目标呢？

还有一个条件是子集中没有元素出现超过2次，如

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

（1出现3次）。但这个条件并不那么重要，违规行为将在我的代码的后面部分被消除。

我认为我的问题有点类似于this，我已经尝试过建议的

filter

，但

filter

仍然循环遍历所有

combination

并且性能是相同的。

Answer 1

解决方案是：

l = [[1], [1,2], [2,3], [3,4], [1,2,3], [1,3,4]]
output = []

for i in range(len(l)):
    l2 = l[:i] + l[i+1:]
    for j in range(len(l2)):
        subset = (l[i], l2[j])
        output.append(subset)
print(output)

#output : [([1], [1, 2]), ([1], [2, 3]), ([1], [3, 4]), ([1], [1, 2, 3]), ([1], [1, 3, 4]), ([1, 2], [1]), ([1, 2], [2, 3]), ([1, 2], [3, 4]), ([1, 2], [1, 2, 3]), ([1, 2], [1, 3, 4]), ([2, 3], [1]), ([2, 3], [1, 2]), ([2, 3], [3, 4]), ([2, 3], [1, 2, 3]), ([2, 3], [1, 3, 4]), ([3, 4], [1]), ([3, 4], [1, 2]), ([3, 4], [2, 3]), ([3, 4], [1, 2, 3]), ([3, 4], [1, 3, 4]), ([1, 2, 3], [1]), ([1, 2, 3], [1, 2]), ([1, 2, 3], [2, 3]), ([1, 2, 3], [3, 4]), ([1, 2, 3], [1, 3, 4]), ([1, 3, 4], [1]), ([1, 3, 4], [1, 2]), ([1, 3, 4], [2, 3]), ([1, 3, 4], [3, 4]), ([1, 3, 4], [1, 2, 3])]