从给定的集合生成一个集合，这样它与所有集合的交集不同于 {} [英] generating a set from given sets such it's intersection with all the sets is different from {}

问题描述

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

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

这篇关于从给定的集合生成一个集合，这样它与所有集合的交集不同于 {}的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！