Skip to main content
 首页 » 编程设计

python之返回所有元素都存在的组合

2025年05月04日9zhwl

我有一个列表说 lis1 = [1,2,3] 和上面列表的子集列表说

lis2 = [[1,2],[2,3],[3],[1],[2]] 

我想生成 lis2 的所有组合,以便 lis1 的所有项目都应该出现在组合中。

例如。这是一个有效的组合

这样的组合之一是 [[1,2],[2,3]](lis1 的所有项目,即 [1,2,3] 存在于其中)

这不是

[[1,2],[1],[2]] # (3 is not present in it) 

我所做的是通过这个函数生成 lis2 的幂集

from itertools import chain, combinations 
 
def powerset(iterable): 
    s = list(iterable) 
    return chain.from_iterable(combinations(s, r) for r in range(1,len(s)+1)) 

但很明显,返回的集合包含类型的组合

[[1,2],[1],[2]] # (3 is not present in it) 

如何检查包含 lis1 所有项目的组合

请您参考如下方法:

您可以应用您的powerset 函数来获取子集的组合并过滤结果:

>>> lis1 = [1,2,3] 
>>> lis2 = [[1,2],[2,3],[3],[1],[2]] 
>>> filter(lambda s: set(sum(s,[])) == set(lis1), powerset(lis2)) 
[([1, 2], [2, 3]), 
 ([1, 2], [3]), 
 ([2, 3], [1]), 
 ([1, 2], [2, 3], [3]), 
 ([1, 2], [2, 3], [1]), 
 ([1, 2], [2, 3], [2]), 
 ([1, 2], [3], [1]), 
 ([1, 2], [3], [2]), 
 ([2, 3], [3], [1]), 
 ([2, 3], [1], [2]), 
 ([3], [1], [2]), 
 ([1, 2], [2, 3], [3], [1]), 
 ([1, 2], [2, 3], [3], [2]), 
 ([1, 2], [2, 3], [1], [2]), 
 ([1, 2], [3], [1], [2]), 
 ([2, 3], [3], [1], [2]), 
 ([1, 2], [2, 3], [3], [1], [2])] 

如果您不希望结果子集中有重复元素,请改用它:

>>> filter(lambda s: sorted(sum(s,[])) == sorted(lis1), powerset(lis2)) 
[([1, 2], [3]), ([2, 3], [1]), ([3], [1], [2])] 

这两种方法都使用 sum(s, [])展平嵌套列表,然后使用 set(全部存在,忽略重复项)或 sorted(全部存在,计数完全相同)将它们与原始元素进行比较。