Python：检查一组是否可以从另一组创建

Question

我有套装清单：graphs = [{1, 2, 3}, {4, 5}, {6}]我必须检查是否input可以将集合创建为内部集合的总和graphs。例如：input1 = {1, 2, 3, 6} # answer - Trueinput2 = {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, 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