时间戳

首页 > 解决方案 > Python：检查是否可以从另一组创建一组

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

问题描述

我有一组列表：

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更大，找到所有组合会有一些问题。

标签： pythonset

解决方案

我认为您以错误的方式看待这个问题。我认为最好删除包含您无法使用的元素的任何集合（即{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

推荐阅读