How do I count the number of common elements in two lists (including duplicates IF in both lists)?

Question

I want to count the number of common elements in two lists, where duplicates are treated separately (i.e. if 'a' is in one list once and the other list twice, it is only counted once, but if it is in both lists twice, it will be counted as 2).

x = [1, 2, 3, 4, 5, 5]  
y = [1, 2, 5, 6, 7, 8]

The number of common elements here would be 3.

x = [1, 2, 3, 4, 5, 5]  
y = [1, 2, 5, 6, 7, 8, 5]

The number of common elements here would be 4.

The closest command I found is

res = sum(i == j for i, j in zip(x, y))

It works except if there are two identical elements in both lists, it will only count them once.

Maybe this would help: https://stackoverflow.com/a/37645155/8801732 — DasaniT, May 15 '23 at 18:07

tdelaney · Answer 1 · 2023-05-15T19:21:20.607

2

You could use collections.Counter to count occurrences in each list. Conveniently, its defined behavior for intersection (the & operator) takes the minimum of each common element, which is exactly the operation you want. Assuming you are python 3.10 or later, it will also sum for you

import collections

x = [1, 2, 3, 4, 5, 5]
y = [1, 2, 5, 6, 7, 8]
result = (collections.Counter(x) & collections.Counter(y)).total()
print(result)

x = [1, 2, 3, 4, 5, 5]
y = [1, 2, 5, 6, 7, 8, 5]
result = (collections.Counter(x) & collections.Counter(y)).total()
print(result)

edited May 15 '23 at 19:21

answered May 15 '23 at 18:20

tdelaney

73,364
6
83
116

`return (x_count & y_count).total()` – Kelly Bundy May 15 '23 at 18:56
@KellyBundy - I wasn't sure what the defined behavior of set-like operations would be, but from the [docs](https://docs.python.org/3/library/collections.html#collections.Counter): _Intersection and union return the minimum and maximum of corresponding counts._. So, yes, that works well. – tdelaney May 15 '23 at 19:14

score -1 · Answer 2 · answered May 15 '23 at 18:01

Here's what I'm talking about. This is sort of a "diff" algorithm. Sort the lists, then go through them one by one, advancing until they go empty.

If the lists are very long, it would be better to keep an index into the lists rather than using .pop(0), but this was simple.

def countdups( l1, l2 ):
    l1 = sorted(l1)
    l2 = sorted(l2)
    dups = 0
    while l1 and l2:
        if l1[0] == l2[0]:
            dups += 1
            l1.pop(0)
            l2.pop(0)
        elif l1[0] < l2[0]:
            l1.pop(0)
        else:
            l2.pop(0)
    return dups

x = [1, 2, 3, 4, 5, 5]
y = [1, 2, 5, 6, 7, 8]
print(countdups(x,y))

x = [1, 2, 3, 4, 5, 5]
y = [1, 2, 5, 6, 7, 8, 5]
print(countdups(x,y))

Output:

3
4

How do I count the number of common elements in two lists (including duplicates IF in both lists)?

2 Answers2