Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Common elements between two lists not using sets in Python

Tags:

python

list

set

I want count the same elements of two lists. Lists can have duplicate elements, so I can't convert this to sets and use & operator.

a=[2,2,1,1]
b=[1,1,3,3]

set(a) & set(b) work
a & b don't work

It is possible to do it withoud set and dictonary?

like image 216
Thomas Avatar asked Apr 28 '10 07:04

Thomas


2 Answers

In Python 3.x (and Python 2.7, when it's released), you can use collections.Counter for this:

>>> from collections import Counter
>>> list((Counter([2,2,1,1]) & Counter([1,3,3,1])).elements())
[1, 1]

Here's an alternative using collections.defaultdict (available in Python 2.5 and later). It has the nice property that the order of the result is deterministic (it essentially corresponds to the order of the second list).

from collections import defaultdict

def list_intersection(list1, list2):
    bag = defaultdict(int)
    for elt in list1:
        bag[elt] += 1

    result = []
    for elt in list2:
        if elt in bag:
            # remove elt from bag, making sure
            # that bag counts are kept positive
            if bag[elt] == 1:
                del bag[elt]
            else:
                bag[elt] -= 1
            result.append(elt)

    return result

For both these solutions, the number of occurrences of any given element x in the output list is the minimum of the numbers of occurrences of x in the two input lists. It's not clear from your question whether this is the behavior that you want.

like image 61
Mark Dickinson Avatar answered Nov 15 '22 18:11

Mark Dickinson


Using sets is the most efficient, but you could always do r = [i for i in l1 if i in l2].

like image 39
Max Shawabkeh Avatar answered Nov 15 '22 18:11

Max Shawabkeh