50

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!

3
  • possible duplicate of Python: How to find list intersection? Commented Apr 8, 2012 at 21:24
  • does your solution have to be recursive? Can you use built-in intersect functions (that is, is this homework?)?
    – K Mehta
    Commented Apr 8, 2012 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
    Commented Apr 8, 2012 at 21:34

7 Answers 7

76

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
6
  • 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
    Commented Apr 8, 2012 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. Commented Apr 8, 2012 at 21:37
  • 2
    Alternatively, result &= s. Commented Apr 8, 2012 at 21:42
  • thank you for your help! it works great and now I know what sets are :)
    – 8bits
    Commented Apr 8, 2012 at 21:55
  • Raymond's answer uses the ability of set.intersection in Python 2.6+ to avoid the loop entirely.
    – agf
    Commented Apr 9, 2012 at 2:47
28

A simple solution (one-line) is:

set.intersection(*[set(list) for list in p])
27

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])
1
  • 1
    The asterisk in set(p[0]).intersection(*p) is an unpacking operator, if anyone is looking for a "googable" term. Commented Aug 16, 2022 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])
1
  • 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
    Commented Apr 9, 2012 at 0: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]
6
  • 1
    Try this with p=[[1,2],[2,1]]. Or even p=[[1,2],[2]].
    – DSM
    Commented Apr 8, 2012 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
    Commented Apr 8, 2012 at 21:55
  • Also, zip will drop elements if the lists vary in length. Commented Apr 8, 2012 at 22:12
  • exactly, sublists not always of the same length, thank you for the help nonetheless!
    – 8bits
    Commented Apr 9, 2012 at 0: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
    Commented Feb 7, 2021 at 11:11
1
reduce(lambda x, y: x & y, (set(i) for i in p))
2
  • 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
    Commented Apr 8, 2012 at 21:31
  • @agf: Understood. Still, it is a working solution (albeit a slightly inefficient one). Commented Apr 8, 2012 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.