2

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

jpp
  • 159,742
  • 34
  • 281
  • 339
Xpack Gunners
  • 43
  • 4
  • You can simply take the union, that way it is guaranteed to that it intersects with all sets, please reformulate your problem, and show your own attempt. – Willem Van Onsem Feb 10 '18 at 23:05
  • 1
    This is a guess, but I think user wants the smallest possible such set. Otherwise the problem is trivial. Needs clarification, though. – jpp Feb 10 '18 at 23:12
  • i'm sorry i forgot to mention that it needs to be as optimal as possible which is why i couldn't solve it – Xpack Gunners Feb 10 '18 at 23:15
  • Have a look at this: https://stackoverflow.com/questions/21973126/set-cover-or-hitting-set-numpy-least-element-combinations-to-make-up-full-set – kjmerf Feb 10 '18 at 23:39

2 Answers2

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 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}]})
jpp
  • 159,742
  • 34
  • 281
  • 339
0

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)
JimmyCarlos
  • 1,934
  • 1
  • 10
  • 24