1

I have a list of n sets of integers denoted as lst = [S1, S2, S3 ... Sn] and I want to find the intersection of all the sets.

Is there an optimal way to do this?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Patrick Connors
  • 5,677
  • 6
  • 27
  • 54

2 Answers2

6

If you have a list sets, you can trivially get their intersection with:

set.intersection(*lst)

This will produce a new set with only those values that are common between all the sets:

>>> lst = [{1, 2, 3}, {3, 5}, {2, 3}]
>>> set.intersection(*lst)
{3}
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
2

Edit: Misread, thought that you have multiple lists of numbers and generally asking how to find those numbers that are present in all of them. Will keep the original answer below, though, as some people still found it helpful to some degree.

Yes, it's called set intersection and can be used on the set data type.

Demo:

>>> s = set((1, 2, 3))
>>> s2 = set((2, 3, 4))
>>> s3 = set((3, 4, 5))
>>> s & s2
{2, 3}
>>> s & s2 & s3
{3}

If your current data is stored in lists, converting it to sets is just a matter of passing the lists to the set() constructor:

>>> numbers = [2, 7, 9, 10]
>>> set(numbers)
{2, 7, 9, 10}

Mind, though, that if a list contains duplicates, that information will get lost, and each duplicated element will only be present once in the resulting intersection.

plamut
  • 3,085
  • 10
  • 29
  • 40
  • This doesn't solve the issue at hand: The OP *has* sets already, but they have a list of sets of arbitrary length. You need to apply this to *all sets in the list*. – Martijn Pieters Jan 08 '18 at 22:15
  • Huh, I apparently missed that, thought that the OP has lists of numbers and wants to find those that are present in all of them. – plamut Jan 08 '18 at 22:17