Intersection of two lists including duplicates?

Question

>>> a = [1,1,1,2,3,4,4]
>>> b = [1,1,2,3,3,3,4]

[1,1,2,3,4]

Please note this is not the same question as this: Python intersection of two lists keeping duplicates Because even though there are three 1s in list a, there are only two in list b so the result should only have two.

Answer 1

You can use collections.Counter for this, which will provide the lowest count found in either list for each element when you take the intersection.

from collections import Counter

c = list((Counter(a) & Counter(b)).elements())

Outputs:

[1, 1, 2, 3, 4]

Answer 2

Simple with no additional imports and easy to debug :)

Disadvantage: The value of list b is changed. Work on a copy of b if you don't want to change b.

c = list()
for x in a:
    if x in b:
        b.remove(x)
        c.append(x)

Answer 3

The accepted solution posted using Counter is simple, but I think this approach using a dictionary will work too and can be faster -- even on lists that aren't ordered (that requirement wasn't really mentioned, but at least one of the other solutions assumes that is the case).

a = [1, 1, 1, 2, 3, 4, 4]
b = [1, 1, 2, 3, 3, 3, 4]
    
def intersect(nums1, nums2):
    match = {}
    for x in a:
        if x in match:
            match[x] += 1
        else:
            match[x] = 1
            
    i = []
    for x in b:
        if x in match:
            i.append(x)
            match[x] -= 1
            if match[x] == 0:
                del match[x]

    return i

def intersect2(nums1, nums2):
    return list((Counter(nums1) & Counter(nums2)).elements())

timeit intersect(a,b)
100000 loops, best of 3: 3.8 µs per loop

timeit intersect2(a,b)
The slowest run took 4.90 times longer than the fastest. This could mean 
that an intermediate result is being cached.
10000 loops, best of 3: 20.4 µs per loop

I tested with lists of random ints of size 1000 and 10000 and it was faster there too.

a = [random.randint(0,100) for r in xrange(10000)]
b = [random.randint(0,100) for r in xrange(1000)]

timeit intersect(a,b)
100 loops, best of 3: 2.35 ms per loop

timeit intersect2(a,b)
100 loops, best of 3: 4.2 ms per loop

And larger lists that would have more common elements

a = [random.randint(0,10) for r in xrange(10000)]
b = [random.randint(0,10) for r in xrange(1000)]

timeit intersect(a,b)
100 loops, best of 3: 2.07 ms per loop

timeit intersect2(a,b)
100 loops, best of 3: 3.41 ms per loop

Answer 4

This should also works.

a = [1, 1, 1, 2, 3, 4, 4]
b = [1, 1, 2, 3, 3, 3, 4]
c = []
i, j = 0, 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        c.append(a[i])
        i += 1
        j += 1
    elif a[i] > b[j]:
        j += 1
    else:
        i += 1

print(c) # [1, 1, 2, 3, 4]