11

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?

Andy Lester
  • 91,102
  • 13
  • 100
  • 152
Thomas
  • 111
  • 1
  • 1
  • 3

3 Answers3

12

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.

Mark Dickinson
  • 29,088
  • 9
  • 83
  • 120
  • `if bag[elt]:` adds an item `elt: 0` to the bag when `elt in bag` is false. When (as the OP hinted) there are few duplicates, it may be better to do `if elt in bag and bag[elt]:` otherwise bag may become bloated with useless 0 values. – John Machin Apr 28 '10 at 10:58
  • @John Machin: Hmm. Good point. An alternative would be to make sure that bag counts are always strictly positive, by following `bag[elt] -= 1` with an `if not bag[elt]: del bag[elt]`. Then the `if` test could just be `if elt in bag:`, which reads more nicely. I'll edit the answer. – Mark Dickinson Apr 28 '10 at 11:10
8

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

Max Shawabkeh
  • 37,799
  • 10
  • 82
  • 91
  • A distinct difference: The suggested set() & set() method will return a single value that is common between the two lists (set([1]) in this example) whereas your solution will return [1, 1] and so on. – Nick Presta Apr 28 '10 at 08:03
  • Thanks, but is it some more perfomence solution? – Thomas Apr 28 '10 at 08:03
  • I want function which return [1,1] – Thomas Apr 28 '10 at 08:05
  • @Thomas: This solution gives `[1, 1]` if `l1 == [1, 1]` and `l2 == [1]`, but it gives `[1]` if `l1 == [1]` and `l2 == [1, 1]`. Is that the behavior that you want? – Mark Dickinson Apr 28 '10 at 10:42
0

SilentGhost, Mark Dickinson and Lo'oris are right, Thanks very much for report this problem - I need common part of lists, so for:

a=[1,1,1,2]

b=[1,1,3,3]

result should be [1,1]

Sorry for comment in not suitable place - I have registered today.

I modified yours solutions:

def count_common(l1,l2):
        l2_copy=list(l2)
        counter=0
        for i in l1:
            if i in l2_copy:
                counter+=1
                l2_copy.remove(i)
        return counter

l1=[1,1,1]
l2=[1,2]
print count_common(l1,l2)

1

Thomas
  • 81
  • 1
  • 6
  • 4
    welcome! You might want to email `team@stackoverflow.com` and ask them to merge your newly registered account with the previous temporary account. See: http://meta.stackexchange.com/questions/18232/how-can-one-link-merge-combine-associate-two-stack-overflow-accounts-users-anon – Mark Dickinson Apr 28 '10 at 13:01