本文介绍了从给定的集合生成一个集合,这样它与所有集合的交集不同于 {}的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我一直在尝试找出一种有效的算法来返回一个集合,例如它与给定集合的交集不等于 {}.
i have been trying to figure out an effective algorithm that returns a set such as it's intersection with the given sets isn't equal to {}.
例如:假设给定的集合是 {1,7,4},{2,8,5},{1,3},{2,6} 函数必须返回集合 {1,2} 因为它与所有给定的集合有一个交点(生成的集合需要尽可能小)
for example : let's say the given sets are {1,7,4},{2,8,5},{1,3},{2,6} the function must return the set {1,2} because it has an intersection point with all the given sets (the generated set needs to be as small as possible)
推荐答案这是一个蛮力解决方案.显然,这是众所周知的NP-complete问题命中集.
This is a brute force solution. Apparently, this is the well-known NP-complete problem 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}]})更多推荐
从给定的集合生成一个集合,这样它与所有集合的交集不同于 {}
发布评论