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

我认为你看待这个问题的方式是错误的。我认为最好删除包含无法使用的元素的任何集合（即{4,5}在查找时删除集合{1,2,3,4}。然后创建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, chaindef 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 Falsegraphs = [{1, 2, 3}, {4, 5}, {6}]input1 = {1, 2, 3, 6}input2 = {1, 2, 3, 4}print(check(graphs, input1))print(check(graphs, input2))印刷：TrueFalse