Compare lists to find common elements in python [duplicate]

Question

Possible Duplicate:
Python - Intersection of two lists

i'm trying to compare two lists in order to find the number of elements they have in common.

The main problem I'm having is when either list contains repeated elements, for example

A = [1,1,1,1]   and  
B = [1,1,2,3]

using the code

n = 0
for x in A:
   if x in B:
      n += 1
print n

gives me the output that n = 4, as technically all elements of A are in B

I'd like to get the output that n = 2, preferably without using sets, Is there anyway I can adapt my code, or a new way of thinking about the problem to achieve this?

Thanks

Answer 1

It's not entirely clear what your specification is, but if you want the number of elements in A that appear in B, without regard to order, but with regard to multiplicity, use collections.Counter:

>>> from collections import Counter
>>> A = [1,1,1,1]
>>> B = [1,1,2,3]
>>> C = Counter(A) & Counter(B)
>>> sum(C.itervalues())
2
>>> list(C.elements())
[1, 1]

Answer 2

Here is an efficient (O(n logn)) way to do it without using sets:

def count_common(a, b):
  ret = 0
  a = sorted(a)
  b = sorted(b)
  i = j = 0
  while i < len(a) and j < len(b):
    c = cmp(a[i], b[j])
    if c == 0:
      ret += 1
    if c <= 0:
      i += 1
    if c >= 0:
      j += 1
  return ret

print count_common([1,1,1,1], [1,1,2,3])

If your lists are always sorted, as they are in your example, you can drop the two sorted() calls. This would give an O(n) algorithm.