46

I'm trying to figure out how to compare an n number of lists to find the common elements. For example:

p=[ [1,2,3],
    [1,9,9],
      ..
      ..
    [1,2,4]

>> print common(p)
>> [1]

Now if I know the number of elements I can do comparions like:

for a in b:
  for c in d:
    for x in y:
...

but that wont work if I don't know how many elements p has. I've looked at this solution that compares two lists https://stackoverflow.com/a/1388864/1320800

but after spending 4 hrs trying to figure a way to make that recursive, a solution still eludes me so any help would be highly appreciated!

Community
  • 1
  • 1
8bits
  • 463
  • 1
  • 4
  • 5
  • possible duplicate of [Python: How to find list intersection?](http://stackoverflow.com/questions/3697432/python-how-to-find-list-intersection) – Daniel A. White Apr 08 '12 at 21:24
  • does your solution have to be recursive? Can you use built-in `intersect` functions (that is, is this homework?)? – K Mehta Apr 08 '12 at 21:27
  • I didn't know that the proper term was "intersection" so thanks for that. It will help me look into it more. Now, it doesn't have to be recursive but we just learned about recursion so I figured that probably I would have to compare p[0] and p[1] and then feed the result to the rest of the elements, that's why I thought that probably it would be a recursive solution – 8bits Apr 08 '12 at 21:34

7 Answers7

69

You are looking for the set intersection of all the sublists, and the data type you should use for set operations is a set:

result = set(p[0])
for s in p[1:]:
    result.intersection_update(s)
print result
Sven Marnach
  • 574,206
  • 118
  • 941
  • 841
  • Thanks for the reply.. I knew nothing about sets so I'm going to research some more. However from a preliminary test p = [[1,2,3], [1,3], [8,1]] the solution you proposed instead of [1] it returns [8,1] ? – 8bits Apr 08 '12 at 21:34
  • @user1320800: The first version of this answer had a wrong `print` statement in the end. Of course we must print `result`, not `s`. – Sven Marnach Apr 08 '12 at 21:37
  • 2
    Alternatively, `result &= s`. – Joel Cornett Apr 08 '12 at 21:42
  • thank you for your help! it works great and now I know what sets are :) – 8bits Apr 08 '12 at 21:55
  • [Raymond's answer](http://stackoverflow.com/a/10067138/500584) uses the ability of `set.intersection` in Python 2.6+ to avoid the loop entirely. – agf Apr 09 '12 at 02:47
  • Adding to @JoelCornett 's comment, you can use `result &= set(s)` instead of `result.intersection_update(s)`. – Box Box Box Box Oct 20 '18 at 09:21
29

A simple solution (one-line) is:

set.intersection(*[set(list) for list in p])
WindChimes
  • 2,955
  • 4
  • 25
  • 26
26

The set.intersection() method supports intersecting multiple inputs at a time. Use argument unpacking to pull the sublists out of the outer list and pass them into set.intersection() as separate arguments:

>>> p=[ [1,2,3],
        [1,9,9],
        [1,2,4]]

>>> set(p[0]).intersection(*p)
set([1])
Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485
  • 1
    The asterisk in `set(p[0]).intersection(*p)` is an unpacking operator, if anyone is looking for a "googable" term. – Alex Witsil Aug 16 '22 at 14:27
17

Why not just:

set.intersection(*map(set, p))

Result:

set([1])

Or like this:

ip = iter(p)
s = set(next(ip))
s.intersection(*ip)

Result:

set([1])

edit:

copied from console:

>>> p = [[1,2,3], [1,9,9], [1,2,4]]
>>> set.intersection(*map(set, p))
set([1])
>>> ip = iter(p)
>>> s = set(next(ip))
>>> s.intersection(*ip)
set([1])
pillmuncher
  • 10,094
  • 2
  • 35
  • 33
  • I don't know if I'm missing something but passing p=[ [1,2,3], [1,9,9], [1,2,4]] didn't seem to work – 8bits Apr 09 '12 at 00:17
3
p=[ [1,2,3],
    [1,9,9],
    [1,2,4]]

ans = [ele[0] for ele in zip(*p) if len(set(ele)) == 1]

Result:

>>> ans
[1]
Akavall
  • 82,592
  • 51
  • 207
  • 251
  • 1
    Try this with p=[[1,2],[2,1]]. Or even p=[[1,2],[2]]. – DSM Apr 08 '12 at 21:42
  • My code only works, if we a looking at all common elements that are also in the same position; that's the whole gist of the zip(*p) thing. That's what I thought OP wanted, but reading the post again, I probably misunderstood. I also assumed that every sublist has the same length. – Akavall Apr 08 '12 at 21:55
  • Also, `zip` will drop elements if the lists vary in length. – Joel Cornett Apr 08 '12 at 22:12
  • exactly, sublists not always of the same length, thank you for the help nonetheless! – 8bits Apr 09 '12 at 00:11
  • This is a really great answer for a different problem. I use this to find common columns : [len(set(c))==1 for c in zip(*p)] – Konchog Feb 07 '21 at 11:11
  • eg, to get the indices of each common column (as a list)... [i for i,c in enumerate(zip(*q)) if len(set(c))==1] – Konchog Feb 07 '21 at 11:18
2
reduce(lambda x, y: x & y, (set(i) for i in p))
Joel Cornett
  • 24,192
  • 9
  • 66
  • 88
  • 1
    `reduce` isn't considered "Pythonic" by many. Also, your version requires each list be converted to a set, and an additional new set to be created for each intersection. Sven's version creates only one set. – agf Apr 08 '12 at 21:31
  • @agf: Understood. Still, it is a working solution (albeit a slightly inefficient one). – Joel Cornett Apr 08 '12 at 21:37
0

You are looking for the set intersection of all the sublists, and the data type you should use for set operations is a set:

result = set(p[0])  
for s in p[1:]:
   result.intersection_update(s)
print result

However, there is a limitation of 10 lists in a list. Anything bigger causes 'result' list to be out of order. Assuming you've made 'result' into a list by list(result).

Make sure you result.sort() to ensure it's ordered if you depend on it to be that way.

spearna
  • 25
  • 9