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

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

例如:假设给定的集合是 {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}]})