how to return the intersection of all possible combinations of n different lists

Question

I was wondering if there is an algorithm that can return the intersection of all possible combinations of n different lists. My example is the following with n = 3 different lists:

list1 = [1,2,3,4,5]
list2 = [1,3,5]
list3 = [1,2,5]

the outcome should look like this:

list1_2_intersection = [1,3,5]
list1_3_intersection = [1,2,5]
list2_3_intersection = [1,5]
list1_2_3_intersection = [1,5]

I was thinking to first use combination to get all possible combinations of n sets and use that to create intersections using intersection manually. However, since I have 6 different sets this seems very time consuming, which is why I was wondering if there is a more efficient way to compute this. Thanks in advance! :)

Where are your sets coming from? In your example, they are all individual set variables, not some iterable with a number of sets - which greatly limits what you can do efficiently in code. If you need something that works on individual variables only, it's simply `set1 & set2 & set3` - except that what you shared in your example aren't sets, they're tuples. So in your case, you'd have to do `tuple(set(set1) & set(set2) & set(set3))` which is very roundabout. — Grismar, Dec 26 '21 at 11:47
Yes, you're right, they're orignially lists. I have 6 individual set variables. Is there a way I could create an iterable out of those individual set variables? — Alex L, Dec 26 '21 at 11:50
Brute force for six such tiny sets will still be quite fast. — Kelly Bundy, Dec 26 '21 at 12:08

score 1 · Answer 1 · answered Dec 26 '21 at 14:40

If you have all sets in a list, you can use the more-itertools-package (pip install more-itertools), which is based on itertools, to get all combinations of those elements using more_itertools.powerset, as is done in this post.

Then getting the intersection is a matter of using set.intersection as you point out yourself. So a solution can look like this

from more_itertools import powerset

sets = [{1,2,3,4,5},{1,3,5},{1,2,5}]
pwset = powerset(sets)
res = [c[0].intersection(*c[1:]) if len(c)>1 else c for c in pwset]

Grismar · Answer 2 · 2021-12-26T23:22:29.017

If you just load or define the sets in an iterable like a list:

my_sets = [
    {1, 2, 3, 4, 5},
    {1, 3, 5},
    {1, 2, 5}
]

my_set_intersection = set.intersection(*my_sets)
print(my_set_intersection)

Of course, the print is just there to show the result, which is in my_set_intersection

If you just have a couple of sets:

set1 = {1, 2, 3, 4, 5},
set2 = {1, 3, 5},
set3 = {1, 2, 5}

intersection_123 = set1 & set2 & set3
# or:
intersection_123 = set.intersection(set1, set2, set3)

For all possible intersections of combinations of all possible sizes of a group of sets:

from itertools import combinations

my_sets = [
    {1, 2, 3, 4, 5},
    {1, 3, 5},
    {1, 2, 5}
]

all_intersections = [set.intersection(*x) for n in range(len(my_sets)) for x in combinations(my_sets, n+1)]

print(all_intersections)

Result:

[{1, 2, 3, 4, 5}, {1, 3, 5}, {1, 2, 5}, {1, 3, 5}, {1, 2, 5}, {1, 5}, {1, 5}]

If you don't like the duplicates (because different combinations of sets can yield the same intersection), you can of course just make the list a set instead.

Note that this is similar to the solution using more_itertools, but I don't like requiring a third party library for something as trivial as generating a powerset (although it may perform better if well-written, which may matter for extremely large sets).

Also note that this leaves out the empty set (the intersection of a combination of size 0), but that's trivial to add of course.

But these results only return the intersections of all sets. However, I'm trying to find a way to get all possible intersections of n different sets. — Alex L, Dec 26 '21 at 12:00
I'm currently working on a network and I want to assign each node a categorical variable. I have 6 different categorical variables (these are my sets). However, I also need the intersections of all possible combinations of my 6 different sets. — Alex L, Dec 26 '21 at 12:27
*"you can of course just make the list a set instead"* - If you also change the inner sets to something hashable. — Kelly Bundy, Dec 26 '21 at 23:30

how to return the intersection of all possible combinations of n different lists

2 Answers2