3

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

Community
  • 1
  • 1
user1876831
  • 31
  • 1
  • 5
  • 3
    Is there a particular reason to avoid using sets? They seem to offer the perfect solution: `len(set(A)&set(B))` – Blckknght Dec 04 '12 at 19:38
  • not particularly, its just that its a question from a revision sheet, and we haven't actually used sets yet – user1876831 Dec 04 '12 at 19:39
  • 1
    Are you sure that you want the answer to be 2 for the example you gave, rather than 1? There's only a single value that's present in both lists (the number 1). If the sets were `[1,2,3,3]` and `[1,1,2,3]` what would you want the count to be? – Blckknght Dec 04 '12 at 19:52
  • Yes, in the example I gave, two of the elements are both present in both lists, while they are both 1, they are two elements present in both lists. In your example I'd like the output to be 3, as the 1, 2, and 3 in the first list are all present in the second – user1876831 Dec 04 '12 at 20:04

4 Answers4

6

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]
Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
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.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • I tested this on sorted arrays, without the `sorted()` calls, fully typed and compiled with Cython, and it is slower that a simple `sorted(set(a) & set(b))`, even with > 1e10 random elements. Plus the latter does not require the initial lists to be sorted. – JulienD Jan 07 '16 at 14:04
1

Here's an entirely different way of thinking about the problem.

Imagine I've got two words, "hello" and "world". To find the common elements, I could iterate through "hello", giving me ['h', 'e', 'l', 'l', 'o']. For each element in the list, I'm going to remove it from the second list(word).

  1. Is 'h' in ['w', 'o', 'r', 'l', 'd']? No.
  2. Is 'e' in ['w', 'o', 'r', 'l', 'd']? No.
  3. Is 'l' in ['w', 'o', 'r', 'l', 'd']? Yes!
  4. Remove it from "world", giving me ['w', 'o', 'r', 'd'].
  5. is 'l' in ['w', 'o', 'r', 'd']? No.
  6. Is 'o' in ['w', 'o', 'r', 'd']?
  7. Yes! Remove it ['w', 'o', 'r', 'd'], giving me ['w', 'r', 'd']

Compare the length of the original object (make sure you've kept a copy around) to the newly generated object and you will see a difference of 2, indicating 2 common letters.

kreativitea
  • 1,741
  • 12
  • 14
  • That's a very good and completely different way of tackling it, I think I'll try and use this in my code. Many thanks! – user1876831 Dec 04 '12 at 20:06
0

So you want the program to check whether only elements at the same indices in the two lists are equal? That would be pretty simple: Just iterate over the length of the two arrays (which I presume, are supposed to be of the same length), say using a variable i, and compare each by the A.index(i) and B.index(i) functions. If you'd like, I could post the code.

If this is not what you want to do, please do make your problem clearer.

Ali
  • 56
  • 1