2

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

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

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

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

一种这样的组合是（其中包含ie的[[1,2],[2,3]]所有项目）lis1[1,2,3]

而这不是

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

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

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 的所有项目的组合

4

1 回答 1

1

您可以应用您的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])]

Both methods use sum(s, []) to flatten the nested lists and then compare those to the original elements using either set (all present, ignore duplicates) or sorted (all present, exact same count).

于 2014-07-28T10:21:39.920 回答