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

本文介绍了从给定的集合生成一个集合，这样它与所有集合的交集不同于 {}的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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}]})