In Python, How can one subtract two non-unique, unordered lists? Say we have
a = [0,1,2,1,0]
b = [0, 1, 1]
c = a - b
O(n log n)
Python 2.7 and 3.2 will add the collections.Counter class which is a dictionary that maps elements to the number of occurrences of the element. This can be used as a multiset.
According to the docs you should be able to do something like this (untested, since I do not have either version installed).
from collections import Counter a = Counter(0,1,2,1) b = Counter(0,1,1) print a - b # ignores items in b missing in a # check every element in a is in b # a[key] returns 0 if key not in a, instead of raising an exception assert all(a[key] > b[key] for key in b)
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.