Python:检查是否可以从另一个集合创建一个集合

Question

我有集合列表：

graphs = [{1, 2, 3}, {4, 5}, {6}]

我必须检查input集合是否可以创建为graphs内部集合的总和
例如：

input1 = {1, 2, 3, 6} # answer - True
input2 = {1, 2, 3, 4} # answer - False, because "4" is only a part of another set, only combinations of full sets are required 

换句话说，graphs:内部存在所有集合的组合

{1, 2, 3}
{4, 5}
{6}
{1, 2, 3, 6}
{1, 2, 3, 4, 5}
{4, 5, 6}
{1, 2, 3, 4, 5, 6}

我需要知道，这些组合中的一个是否等于input。

我应该如何正确地迭代graphs元素以获得答案？如果graphs较大，则在查找所有组合时会出现一些问题。

Answer 1

我认为您对此的看法是错误的。我认为最好删除任何包含无法使用的元素的集合(即，在查找{1,2,3,4}时删除集合{4,5}。然后创建所有其他集合的union，看看这是否等于您的输入集合。

这样，你就不需要找到所有的组合，只需要一个(最多(O(n*len(sets((消除步骤。

graphs = [i for i in graphs if i.issubset(input1)  ]

检查答案：

result = set().union(*graphs) == input1

Answer 2

您可以找到itertools.combinations的所有组合，然后简单地比较集合：

from itertools import combinations, chain
def check(graphs, inp):
    for i in range(1, len(graphs)+1):
        for p in combinations(graphs, i):
            if set(chain(*p)) == inp:
                return True
    return False
graphs = [{1, 2, 3}, {4, 5}, {6}]
input1 = {1, 2, 3, 6}
input2 = {1, 2, 3, 4}
print(check(graphs, input1))
print(check(graphs, input2))

打印：

True
False