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 {}. for example : let's say the given sets a

Solution 1:

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 inrange(1, len(U)):
    combs = combinations(U, i)
    for c in combs:
        ifall(set(c) & l for l in A):
            result[len(c)].append(set(c))
    if result:
        break

result
# defaultdict(list, {2: [{1, 2}]})

Solution 2:

Is it necessary to make the combinedSet as small as possible? If not, this would work:

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

Alternative, more concise method as suggested in comments:

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