用Python减去两个列表

Question

在Python中，如何减去两个非唯一的无序列表？假设我们有a = [0,1,2,1,0]和b = [0, 1, 1]我想这样做c = a - b，并有c成为[2, 0]或[0, 2]顺序无关紧要给我。如果a在b中不包含所有元素，则应该抛出异常。

请注意，这与套装不同！ 我对找到a和b中的元素集的差异不感兴趣，而对a和b中元素的实际集合之间的差异感兴趣。

我可以使用for循环来执行此操作，在a中查找b的第一个元素，然后从b和a中删除该元素，依此类推。但这对我没有吸引力，这会非常低效（按O(n^2)时间顺序）及时执行此操作应该没问题O(n log n)。

Answer 1

Python
2.7和3.2添加了collections.Counter该类，它是一个字典子类，可将元素映射到该元素的出现次数。可以用作多集。您可以执行以下操作：

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]

同样，如果您要检查其中的每个元素b都在中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)

但是由于您坚持使用2.5，因此可以尝试将其导入并定义自己的版本（如果失败）。这样，您将确保获得最新版本（如果有），如果没有，则回落到可用版本。如果将来将其转换为C实现，您还将从速度改进中受益。

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

您可以在此处找到当前的Python源。