52

In Python, How can one subtract two non-unique, unordered lists? Say we have a = [0,1,2,1,0] and b = [0, 1, 1] I'd like to do something like c = a - b and have c be [2, 0] or [0, 2] order doesn't matter to me. This should throw an exception if a does not contain all elements in b.

Note this is different from sets! I'm not interested in finding the difference of the sets of elements in a and b, I'm interested in the difference between the actual collections of elements in a and b.

I can do this with a for loop, looking up the first element of b in a and then removing the element from b and from a, etc. But this doesn't appeal to me, it would be very inefficient (order of O(n^2) time) while it should be no problem to do this in O(n log n) time.

1
  • 1
    Also note that anything that operates directly out of unordered lists will be n^2 (len(a) * len(b)). To do it efficiently, you'll either need an intermediate data structure (eg. a dict counting occurances of each value) or to sort the lists first. If you're only dealing with small lists, it won't matter. Jan 15, 2010 at 11:51

13 Answers 13

66

I know "for" is not what you want, but it's simple and clear:

for x in b:
  a.remove(x)

Or if members of b might not be in a then use:

for x in b:
  if x in a:
    a.remove(x)
0
42

I would do it in an easier way:

a_b = [e for e in a if not e in b ]

..as wich wrote, this is wrong - it works only if the items are unique in the lists. And if they are, it's better to use

a_b = list(set(a) - set(b))
0
36

Python 2.7 and 3.2 added the collections.Counter class, which is a dictionary subclass that maps elements to the number of occurrences of the element. This can be used as a multiset. You can do something like this:

from collections import Counter
a = Counter([0, 1, 2, 1, 0])
b = Counter([0, 1, 1])
c = a - b  # ignores items in b missing in a

print(list(c.elements()))  # -> [0, 2]

As well, if you want to check that every element in b is in a:

# a[key] returns 0 if key not in a, instead of raising an exception
assert all(a[key] >= b[key] for key in b)

But since you are stuck with 2.5, you could try importing it and define your own version if that fails. That way you will be sure to get the latest version if it is available, and fall back to a working version if not. You will also benefit from speed improvements if if gets converted to a C implementation in the future.

try:
   from collections import Counter
except ImportError:
    class Counter(dict):
       ...

You can find the current Python source here.

0
6

I'm not sure what the objection to a for loop is: there is no multiset in Python so you can't use a builtin container to help you out.

Seems to me anything on one line (if possible) will probably be helishly complex to understand. Go for readability and KISS. Python is not C :)

5

Python 2.7+ and 3.0 have collections.Counter (a.k.a. multiset). The documentation links to Recipe 576611: Counter class for Python 2.5:

from operator import itemgetter
from heapq import nlargest
from itertools import repeat, ifilter

class Counter(dict):
    '''Dict subclass for counting hashable objects.  Sometimes called a bag
    or multiset.  Elements are stored as dictionary keys and their counts
    are stored as dictionary values.

    >>> Counter('zyzygy')
    Counter({'y': 3, 'z': 2, 'g': 1})

    '''

    def __init__(self, iterable=None, **kwds):
        '''Create a new, empty Counter object.  And if given, count elements
        from an input iterable.  Or, initialize the count from another mapping
        of elements to their counts.

        >>> c = Counter()                           # a new, empty counter
        >>> c = Counter('gallahad')                 # a new counter from an iterable
        >>> c = Counter({'a': 4, 'b': 2})           # a new counter from a mapping
        >>> c = Counter(a=4, b=2)                   # a new counter from keyword args

        '''        
        self.update(iterable, **kwds)

    def __missing__(self, key):
        return 0

    def most_common(self, n=None):
        '''List the n most common elements and their counts from the most
        common to the least.  If n is None, then list all element counts.

        >>> Counter('abracadabra').most_common(3)
        [('a', 5), ('r', 2), ('b', 2)]

        '''        
        if n is None:
            return sorted(self.iteritems(), key=itemgetter(1), reverse=True)
        return nlargest(n, self.iteritems(), key=itemgetter(1))

    def elements(self):
        '''Iterator over elements repeating each as many times as its count.

        >>> c = Counter('ABCABC')
        >>> sorted(c.elements())
        ['A', 'A', 'B', 'B', 'C', 'C']

        If an element's count has been set to zero or is a negative number,
        elements() will ignore it.

        '''
        for elem, count in self.iteritems():
            for _ in repeat(None, count):
                yield elem

    # Override dict methods where the meaning changes for Counter objects.

    @classmethod
    def fromkeys(cls, iterable, v=None):
        raise NotImplementedError(
            'Counter.fromkeys() is undefined.  Use Counter(iterable) instead.')

    def update(self, iterable=None, **kwds):
        '''Like dict.update() but add counts instead of replacing them.

        Source can be an iterable, a dictionary, or another Counter instance.

        >>> c = Counter('which')
        >>> c.update('witch')           # add elements from another iterable
        >>> d = Counter('watch')
        >>> c.update(d)                 # add elements from another counter
        >>> c['h']                      # four 'h' in which, witch, and watch
        4

        '''        
        if iterable is not None:
            if hasattr(iterable, 'iteritems'):
                if self:
                    self_get = self.get
                    for elem, count in iterable.iteritems():
                        self[elem] = self_get(elem, 0) + count
                else:
                    dict.update(self, iterable) # fast path when counter is empty
            else:
                self_get = self.get
                for elem in iterable:
                    self[elem] = self_get(elem, 0) + 1
        if kwds:
            self.update(kwds)

    def copy(self):
        'Like dict.copy() but returns a Counter instance instead of a dict.'
        return Counter(self)

    def __delitem__(self, elem):
        'Like dict.__delitem__() but does not raise KeyError for missing values.'
        if elem in self:
            dict.__delitem__(self, elem)

    def __repr__(self):
        if not self:
            return '%s()' % self.__class__.__name__
        items = ', '.join(map('%r: %r'.__mod__, self.most_common()))
        return '%s({%s})' % (self.__class__.__name__, items)

    # Multiset-style mathematical operations discussed in:
    #       Knuth TAOCP Volume II section 4.6.3 exercise 19
    #       and at http://en.wikipedia.org/wiki/Multiset
    #
    # Outputs guaranteed to only include positive counts.
    #
    # To strip negative and zero counts, add-in an empty counter:
    #       c += Counter()

    def __add__(self, other):
        '''Add counts from two counters.

        >>> Counter('abbb') + Counter('bcc')
        Counter({'b': 4, 'c': 2, 'a': 1})


        '''
        if not isinstance(other, Counter):
            return NotImplemented
        result = Counter()
        for elem in set(self) | set(other):
            newcount = self[elem] + other[elem]
            if newcount > 0:
                result[elem] = newcount
        return result

    def __sub__(self, other):
        ''' Subtract count, but keep only results with positive counts.

        >>> Counter('abbbc') - Counter('bccd')
        Counter({'b': 2, 'a': 1})

        '''
        if not isinstance(other, Counter):
            return NotImplemented
        result = Counter()
        for elem in set(self) | set(other):
            newcount = self[elem] - other[elem]
            if newcount > 0:
                result[elem] = newcount
        return result

    def __or__(self, other):
        '''Union is the maximum of value in either of the input counters.

        >>> Counter('abbb') | Counter('bcc')
        Counter({'b': 3, 'c': 2, 'a': 1})

        '''
        if not isinstance(other, Counter):
            return NotImplemented
        _max = max
        result = Counter()
        for elem in set(self) | set(other):
            newcount = _max(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result

    def __and__(self, other):
        ''' Intersection is the minimum of corresponding counts.

        >>> Counter('abbb') & Counter('bcc')
        Counter({'b': 1})

        '''
        if not isinstance(other, Counter):
            return NotImplemented
        _min = min
        result = Counter()
        if len(self) < len(other):
            self, other = other, self
        for elem in ifilter(self.__contains__, other):
            newcount = _min(self[elem], other[elem])
            if newcount > 0:
                result[elem] = newcount
        return result


if __name__ == '__main__':
    import doctest
    print doctest.testmod()

Then you can write

 a = Counter([0,1,2,1,0])
 b = Counter([0, 1, 1])
 c = a - b
 print list(c.elements())  # [0, 2]
0
4

to use list comprehension:

[i for i in a if not i in b or b.remove(i)]

would do the trick. It would change b in the process though. But I agree with jkp and Dyno Fu that using a for loop would be better.

Perhaps someone can create a better example that uses list comprehension but still is KISS?

0
2

To prove jkp's point that 'anything on one line will probably be helishly complex to understand', I created a one-liner. Please do not mod me down because I understand this is not a solution that you should actually use. It is just for demonstrational purposes.

The idea is to add the values in a one by one, as long as the total times you have added that value does is smaller than the total number of times this value is in a minus the number of times it is in b:

[ value for counter,value in enumerate(a) if a.count(value) >= b.count(value) + a[counter:].count(value) ]

The horror! But perhaps someone can improve on it? Is it even bug free?

Edit: Seeing Devin Jeanpierre comment about using a dictionary datastructure, I came up with this oneliner:

sum([ [value]*count for value,count in {value:a.count(value)-b.count(value) for value in set(a)}.items() ], [])

Better, but still unreadable.

0

You can try something like this:

class mylist(list):

    def __sub__(self, b):
        result = self[:]
        b = b[:]
        while b:
            try:
                result.remove(b.pop())
            except ValueError:
                raise Exception("Not all elements found during subtraction")
        return result


a = mylist([0, 1, 2, 1, 0] )
b = mylist([0, 1, 1])

>>> a - b
[2, 0]

You have to define what [1, 2, 3] - [5, 6] should output though, I guess you want [1, 2, 3] thats why I ignore the ValueError.

Edit: Now I see you wanted an exception if a does not contain all elements, added it instead of passing the ValueError.

5
  • Why are you subclassing list? Jan 15, 2010 at 10:06
  • The OP states that "This should throw an exception if a does not contain all elements in b," so the ValueError shouldn't be silenced. Jan 15, 2010 at 10:07
  • @Devin: because the title of this question is "Subtracting two lists in Python"?
    – mthurlin
    Jan 15, 2010 at 10:11
  • Apart from ignoring the exception (I actually want the excepton) that seems pretty nice, though I wonder about it's performance. remove is O(n) I suspect. Subclassing list itself is a nice way to keep stuff readible yet not clutter the code too much, hadn't even thought of that.
    – wich
    Jan 15, 2010 at 10:11
  • remove is O(n), making it potentially quadratic. It could be faster if you changed your data structure-- why are you using a list rather than a dict (mapping to element counts)? As for subclassing list, it doesn't particularly remove clutter. Really, how different is sub(a, b) and a - b? The difficulty is that you have to be using mylists everywhere instead of lists, which might be painful to track down. Otherwise, it's generally just bad style. In more complex cases (e.g. overriding __getitem__), behavior is wonky because code is shared in C, not Python, so a lot more work is involved. Jan 15, 2010 at 10:31
0

I attempted to find a more elegant solution, but the best I could do was basically the same thing that Dyno Fu said:

from copy import copy

def subtract_lists(a, b):
    """
    >>> a = [0, 1, 2, 1, 0]
    >>> b = [0, 1, 1]
    >>> subtract_lists(a, b)
    [2, 0]

    >>> import random
    >>> size = 10000
    >>> a = [random.randrange(100) for _ in range(size)]
    >>> b = [random.randrange(100) for _ in range(size)]
    >>> c = subtract_lists(a, b)
    >>> assert all((x in a) for x in c)
    """
    a = copy(a)
    for x in b:
        if x in a:
            a.remove(x)
    return a
0

Here's a relatively long but efficient and readable solution. It's O(n).

def list_diff(list1, list2):
    counts = {}
    for x in list1:
        try:
            counts[x] += 1
        except:
            counts[x] = 1
    for x in list2:
        try:
            counts[x] -= 1
            if counts[x] < 0:
                raise ValueError('All elements of list2 not in list2')
        except:
            raise ValueError('All elements of list2 not in list1') 
    result = []
    for k, v in counts.iteritems():
        result += v*[k] 
    return result

a = [0, 1, 1, 2, 0]
b = [0, 1, 1]
%timeit list_diff(a, b)
%timeit list_diff(1000*a, 1000*b)
%timeit list_diff(1000000*a, 1000000*b)
100000 loops, best of 3: 4.8 µs per loop
1000 loops, best of 3: 1.18 ms per loop
1 loops, best of 3: 1.21 s per loop
1
  • I thought dict insert/lookup is O(1). I think that's what it says here wiki.python.org/moin/TimeComplexity. Note how the time grows linearly for these runs: %timeit list_diff(1000*a, 1000*b) 1000 loops, best of 3: 1.26 ms per loop %timeit list_diff(10000*a, 10000*b) 100 loops, best of 3: 12.3 ms per loop %timeit list_diff(100000*a, 100000*b) 10 loops, best of 3: 125 ms per loop %timeit list_diff(1000000*a, 1000000*b) 1 loops, best of 3: 1.18 s per loop Apologies for the hard-to-read format
    – JoeCondron
    Jan 5, 2015 at 10:13
0

You can use the map construct to do this. It looks quite ok, but beware that the map line itself will return a list of Nones.

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

map(lambda x:a.remove(x), b)
a
-3
c = [i for i in b if i not in a]
1
  • I see what you mean now. Indeed, my answer as currently written is not a correct answer to this question. Jul 15, 2013 at 9:07
-4
list(set([x for x in a if x not in b]))
  • Leaves a and b untouched.
  • Is a unique set of "a - b".
  • Done.
1
  • As stated in the question, this is different from sets! the requirement is to not have the "unique set" of a - b but to have a - b
    – wich
    Sep 10, 2012 at 3:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.