Difference Between Two Lists with Duplicates in Python

24
votes

I have two lists that contain many of the same items, including duplicate items. I want to check which items in the first list are not in the second list. For example, I might have one list like this:

l1 = ['a', 'b', 'c', 'b', 'c']

and one list like this:

l2 = ['a', 'b', 'c', 'b']

Comparing these two lists I would want to return a third list like this:

l3 = ['c']

I am currently using some terrible code that I made a while ago that I'm fairly certain doesn't even work properly shown below.

def list_difference(l1,l2):
    for i in range(0, len(l1)):
        for j in range(0, len(l2)):
            if l1[i] == l1[j]:
                l1[i] = 'damn'
                l2[j] = 'damn'
    l3 = []
    for item in l1:
        if item!='damn':
            l3.append(item)
    return l3

How can I better accomplish this task?

6
python
Why l3 = ['c']? letter c is in both l1 and l2 I don't understand - César
Does the order matter? I.e. would [1,2,3,4] and [1,2,4,3] end with a [3,4] or [4,3]? Or do you just want to check that if l1 contains X n-times, then l2 should contain X n-times too (and vice-versa)? - poke
Well, it should work but it's destructive and O(n^2 + n). - user395760
Please define "difference" more clearly. What problem are you trying to solve by getting the difference of the two lists? - Karl Knechtel
@CésarBustíos: there are two 'c' in l1 and only one 'c' in l2 so the difference is ["c"]. - jfs

6 Answers

44
votes

You didn't specify if the order matters. If it does not, you can do this in >= Python 2.7:

l1 = ['a', 'b', 'c', 'b', 'c']
l2 = ['a', 'b', 'c', 'b']

from collections import Counter

c1 = Counter(l1)
c2 = Counter(l2)

diff = c1-c2
print list(diff.elements())
9
votes

Create Counters for both lists, then subtract one from the other.

from collections import Counter

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

c = Counter(a)
c.subtract(Counter(b))
6
votes

To take into account both duplicates and the order of elements:

from collections import Counter

def list_difference(a, b):
    count = Counter(a) # count items in a
    count.subtract(b)  # subtract items that are in b
    diff = []
    for x in a:
        if count[x] > 0:
           count[x] -= 1
           diff.append(x)
    return diff

Example

print(list_difference("z y z x v x y x u".split(), "x y z w z".split()))
# -> ['y', 'x', 'v', 'x', 'u']

Python 2.5 version:

from collections import defaultdict 

def list_difference25(a, b):
    # count items in a
    count = defaultdict(int) # item -> number of occurrences
    for x in a:
        count[x] += 1

    # subtract items that are in b
    for x in b: 
        count[x] -= 1

    diff = []
    for x in a:
        if count[x] > 0:
           count[x] -= 1
           diff.append(x)
    return diff
5
votes

Counters are new in Python 2.7. For a general solution to substract a from b:

def list_difference(b, a):
    c = list(b)
    for item in a:
       try:
           c.remove(item)
       except ValueError:
           pass            #or maybe you want to keep a values here
    return c
0
votes

you can try this

list(filter(lambda x:l1.remove(x),li2)) print(l1)

0
votes

Try this one:

from collections import Counter
from typing import Sequence

def duplicates_difference(a: Sequence, b: Sequence) -> Counter:
    """
    >>> duplicates_difference([1,2],[1,2,2,3])
    Counter({2: 1, 3: 1})
    """
    shorter, longer = sorted([a, b], key=len)
    return Counter(longer) - Counter(shorter)