do list subtraction in python

Question

Possible Duplicate:
Python list subtraction operation

In Python you can concatenate lists like so:

print([3,4,5]+[4,5])

which gives this output:

[3,4,5,4,5]

But what I'm looking for is an equivalent 'subtraction' operation, so that doing something like this:

print([3,4,5]-[4,5])

Will output this:

[3]

However, the subtraction operator isn't defined for lists. I've tried this:

a = [3,4,5]
b = [4,5]
print(list(filter(lambda x : x not in b,a)))

Which works, but I'm uncertain whether or not this is the best way to do this. I would also like to preserve the original item positions

Answer 1

You can easily do this with a list comprehension:

nl = [elem for elem in a if elem not in b]

Edit

Better to use a set to test against. This will remove duplicates from your list.

bb= set(b)
nl = [elem for elem in a if elem not in bb]

Answer 2

This is a somewhat poorly-defined problem. I can think of several non-equivalent definitions of list "subtraction," two of which are already represented: truncating (via slicing) -- a true inverse of concatenation; and filtering, which resembles the definition of "subtraction" (really relative complementation) for sets. For filtering, using a list comprehension over a with b converted to a set is the best approach. (I.e. larsvegas's answer.)

But one version that hasn't been considered is the multiset definition of subtraction. Python's Counter type provides us with a multiset:

>>> from collections import Counter
>>> a = [3, 4, 5]
>>> b = [4, 5]
>>> a_counter = Counter(a)
>>> b_counter = Counter(b)
>>> a_counter
Counter({3: 1, 4: 1, 5: 1})
>>> b_counter
Counter({4: 1, 5: 1})
>>> a_counter - b_counter
Counter({3: 1})

Of course, this doesn't preserve order, but we can fix that by filtering a based on the result of a_counter - b_counter:

def subtract_lists(a, b):
    multiset_difference = Counter(a) - Counter(b)
    result = []
    for i in a:
        if i in multiset_difference:
            result.append(i)
            multiset_difference -= Counter((i,))
    return result

This has several nice properties. It preserves order; it functions as a true inverse of concatenation; it implements an intuitively consistent version of subtraction on a datatype that can contain duplicates; and it works in linear time.

>>> subtract_lists(a, b)
[3]
>>> subtract_lists([1, 2, 3, 4], [2, 3, 4])
[1]
>>> subtract_lists([1, 2, 3, 4], [2, 4])
[1, 3]
>>> subtract_lists([1, 2, 3, 4, 4, 4], [2, 4])
[1, 3, 4, 4]

Answer 3

a = [3,4,5]
b = [4,5]

list(set(a) -  set(b))
[3]

Answer 4

If you mean subtraction as in removing the last elements from the list, then it's quite a simple operation using list slicing:

def list_subtraction(seq, remove):
    l = len(remove)
    if seq[-l:] == remove:
        return seq[:-l]
    else:
        raise ValueError("Subtraction not possible, "
                         "{} is not a tail of {}.".format(remove, seq))

Answer 5

This is of course since it's just appending, which is why the duplicates aren't removed or affected at all.

Subtraction would be just slicing off the end:

a = [3, 4, 5]
b = [4, 5]
c = a + b

d = c[:-len(b)]

This will make d equal a, i.e. [3, 4, 5].

Answer 6

Given:

a = [3, 4, 5]
b = [4, 5]

Then one of the following should work, depending on what you want.

# remove 'b' from the end of 'a' if it's there (strict de-concatenation)
if a[-len(b):] == b:
    a = a[:-len(b)]

# remove any elements from 'a' that are in `b` (including multiples)
bset = set(b)
a = [x for x in a if x not in bset]

# faster version of above but doesn't preserve order
a = list(set(a) - set(b))

# remove elements from 'a' that are in 'b' (one leftmost item only)
bset = set(b)
a = [x for x in a if x not in bset or bset.remove(x)]

# remove elements from 'a' that are in 'b' (one rightmost item only)
bset = set(b)
a = list(reversed([x for x in reversed(a) if x not in bset or bset.remove(x)]))

Answer 7

If you want this to remove things from anywhere in the list, and only remove them as many times as they appear in the second list (so that sub([1, 2, 3, 3, 4, 4, 5], [3, 4, 5]) == [1, 2, 3, 4]), you need to be a little trickier and remove each element from (a copy of) the right-hand list as you use it:

def sub(l, r):
    '''
    Remove all elements in r from l
    '''
    r = r[:]
    res = []
    for a in l:
        try:
            i = r.index(a)
        except ValueError:
            res.append(a)
        else:
            del r[i]
    return res

If you want, eg, [1, 2, 3] - [4] to be an error, you can check after the loop if r is non-empty.