Intersection of two lists including duplicates?

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]

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)

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