我有套裝清單：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更大，找到所有組合就會出現一些問題。
2 回答
婷婷同學_
TA貢獻1844條經驗 獲得超8個贊
我認為你看待這個問題的方式是錯誤的。我認為最好刪除包含無法使用的元素的任何集合（即{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
慕容森
TA貢獻1853條經驗 獲得超18個贊
您可以找到 的所有組合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
添加回答
舉報
0/150
提交
取消