Find Intersection Sets Between List Of Sets

The following question is on python 3.6. Suppose I have lists of sets, for example L1 = [{2,7},{2,7,8},{2,3,6,7},{1,2,4,5,7}] L2 = [{3,6},{1,3,4,6,7},{2,3,5,6,8}]

Solution 1:

You can first calculate all possible intersections between L1 and L2, then calculate the intersections between that set and L3 and so on.

list_generator = iter([  # some generator that produces your lists 
    [{2,7}, {2,7,8}, {2,3,6,7}, {1,2,4,5,7}],      
    [{3,6}, {1,3,4,6,7}, {2,3,5,6,8}],      
    [{2,5,7,8}, {1,2,3,5,7,8}, {2,4,5,6,7,8}], 
])
# for example, you can read from a file:# (adapt the format to your needs)deflist_generator_from_file(filename):
    withopen(filename) as f:
        for line in f:
            yieldlist(map(lambda x: set(x.split(',')), line.strip().split('|')))
# list_generator would be then list_generator_from_file('myfile.dat')

intersections = next(list_generator)  # get first list
new_intersections = set()

for list_ in list_generator:
    for old in intersections:
        for new in list_:
            new_intersections.add(frozenset(old.intersection(new)))
    # at this point we don't need the current list any more
    intersections, new_intersections = new_intersections, set()

print(intersections)

Output looks like {frozenset({7}), frozenset({3, 7}), frozenset({3}), frozenset({6}), frozenset({2, 6}), frozenset({6, 7}), frozenset(), frozenset({8, 2}), frozenset({2, 3}), frozenset({1, 7}), frozenset({4, 7}), frozenset({2, 5}), frozenset({2})}, which matches what you have except for the {1,7} set you missed.

Solution 2:

You can use functools.reduce(set.intersection, sets) to handle variable inputs. And itertools.product(nested_list_of_sets) to generate combinations with one element from each of several sequences.

By using generator functions (yield) and lazy iterators such as itertools.product, you can reduce memory usage by orders of magnitude.

import itertools
import functools

nested_list_of_sets = [
    [{2,7}, {2,7,8}, {2,3,6,7}, {1,2,4,5,7}], 
    [{3,6}, {1,3,4,6,7}, {2,3,5,6,8}],
    [{2,5,7,8}, {1,2,3,5,7,8}, {2,4,5,6,7,8}],
]

deffind_intersections(sets):
    """Take a nested sequence of sets and generate intersections"""for combo in itertools.product(*sets):
        yield (combo, functools.reduce(set.intersection, combo))

for input_sets, output_set in find_intersections(nested_list_of_sets):
    print('{:<55}  ->   {}'.format(repr(input_sets), output_set))

Output is

({2, 7}, {3, 6}, {8, 2, 5, 7})                           ->   set()
({2, 7}, {3, 6}, {1, 2, 3, 5, 7, 8})                     ->   set()
({2, 7}, {3, 6}, {2, 4, 5, 6, 7, 8})                     ->   set()
({2, 7}, {1, 3, 4, 6, 7}, {8, 2, 5, 7})                  ->   {7}
({2, 7}, {1, 3, 4, 6, 7}, {1, 2, 3, 5, 7, 8})            ->   {7}
({2, 7}, {1, 3, 4, 6, 7}, {2, 4, 5, 6, 7, 8})            ->   {7}
({2, 7}, {2, 3, 5, 6, 8}, {8, 2, 5, 7})                  ->   {2}
({2, 7}, {2, 3, 5, 6, 8}, {1, 2, 3, 5, 7, 8})            ->   {2}
# ... etc

Online demo on repl.it

Solution 3:

This may be what you are looking for:

res = {frozenset(frozenset(x) forxin (i, j, k)): i & j & k \
       foriin L1 forjin L2 forkin L3}

Explanation

• frozenset is required because set is not hashable. Dictionary keys must be hashable.
• Cycle through every length-3 combination of items in L1, L2, L3.
• Calculate intersection via & operation, equivalent to set.intersection.