从给定的集合生成一个集合，使它与所有集合相交，这与{}不同

Question

我一直在试图找出一个有效的算法，返回一个集合，比如它与给定集合的交集不等于{}。你知道吗

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

Answer 1

这是一个暴力解决方案。显然，这就是众所周知的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}]})

Answer 2

是否有必要使组合装置尽可能小？如果没有，这将起作用：

A = [{1,7,4},{2,8,5},{1,3},{2,6}]
combinedSet = set()
for a in A:
    combinedSet |= a
print(combinedSet)

另一种更简洁的方法，如评论中所建议的：

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