Common elements between two lists not using sets in Python
Question: 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?


Answer: In Python 3.x (and Python 2.7, when it's released), you can use
[collections.Counter](http://docs.python.org/dev/library/collections.html#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](http://docs.python.org/library/collections.html#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.

