gpt4 book ai didi

python - 从给定集合生成一个集合,使其与所有集合的交集不同于 {}

转载 作者:太空宇宙 更新时间:2023-11-04 04:49:28 25 4
gpt4 key购买 nike

我一直在尝试寻找一种有效的算法来返回一个集合,例如它与给定集合的交集不等于 {}

例如:假设给定的集合是 {1,7,4},{2,8,5},{1,3},{2,6} 函数必须返回集合 {1,2} 因为它与所有给定集合有一个交点(生成的集合需要尽可能小)

最佳答案

这是一个蛮力解决方案。显然,这就是众所周知的 NP-complete问题 Hitting Set .

from itertools import combinations
from collections import defaultdict

A = [{1,7,4},{2,8,5},{1,3},{2,6}]
U = set.union(*A)

result = defaultdict(list)

for i in range(1, len(U)):
combs = combinations(U, i)
for c in combs:
if all(set(c) & l for l in A):
result[len(c)].append(set(c))
if result:
break

result
# defaultdict(list, {2: [{1, 2}]})

关于python - 从给定集合生成一个集合,使其与所有集合的交集不同于 {},我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48726509/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com