Python 列表减法运算关于重复

Question

我想从另一个列表中减去一个列表，但要考虑重复：

>>> a = ['a', 'b', 'c','c', 'c', 'c', 'd', 'e', 'e']
>>> b = ['a', 'c', 'e', 'f','c']
>>> a - b
['b', 'c','c', 'd', 'e']

元素的顺序无关紧要。

有一个问题有答案 here 但它忽略了重复。那里的解决方案将给出：

>>> a - b
['b', 'd']

一个解决方案考虑重复但它改变了原始列表之一：

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

我写了这个解决方案：

a_sub_b = list(a)
b_sub_a = list(b)
for e in a:
    if e in b_sub_a:
        a_sub_b.remove(e)
        b_sub_a.remove(e)

print a_sub_b # a - b 
print b_sub_a # b - a

这对我有用，但是否有更好、更简单或更有效的解决方案？

Answer 1

这将针对 a 的每个元素搜索 b 的每个元素。它还将为每个匹配的元素在每个列表上执行线性 remove。因此，您的算法需要二次方时间——O(max(N, M)^2)，其中 N 是 a 的长度，M 是 b 的长度。

如果您只是将 b 复制到 set 而不是 list，就可以解决问题。现在，您只需对 a 中的每个元素进行恒定时间集查找，并进行恒定时间集删除而不是列表删除。但是您仍然遇到线性时间问题和从 a 副本中错误删除的问题。而且您不能只将 a 复制到 set，因为那样会丢失重复项。

除此之外，a_sub_b.remove(e) 删除了 一个匹配 e 的元素。这不一定与 您刚刚查找的元素 相同。它将是一个 equal 元素，如果身份根本不重要，那很好……但如果重要，那么 remove 可能会做错事。

无论如何，性能已经是不使用 remove 的充分理由。一旦您解决了上述问题，这就是使您的算法成为二次而非线性算法的唯一方法。

解决此问题的最简单方法是建立一个新列表，而不是复制列表并从中删除。

解决这两个问题，你有 O(2N+M) 时间，这是线性的。

因此，将两者放在一起：

b_set = set(b)
new_a = []
for element in a:
    if a in b_set:
        b_set.remove(element)
    else:
        new_a.append(element)

不过，这还是有问题。你没有把事情说得很清楚，所以很难确定，但是 b 可以包含重复项，如果是这样，是否意味着重复的元素应该从 a 中多次删除？如果是这样，您需要一个多集，而不是 set。在 Python 中最简单的方法是使用 Counter:

from collections import Counter

b_counts = Counter(b)
new_a = []
for element in a:
    if b_counts[element]:
        b_counts[element] -= 1
    else:
        new_a.append(element)

另一方面，如果 a 和 b 的顺序都不重要，这就减少了多重差异，这使得它更容易：

new_a = list((Counter(a) - Counter(b)).elements())

但实际上，如果两者的顺序毫无意义，您可能首先应该使用 Counter 或其他多重表示，而不是列表……

Answer 2

如果顺序无关紧要，请使用 collections.Counter:

c = list((Counter(a) - Counter(b)).elements())

Counter(a) - Counter(b)构建一个Counter，其中元素x的计数等于x在a中出现的次数减去[=13]的次数=] 出现在 b 中。 elements() 创建一个迭代器，它生成每个元素的次数等于它的计数，然后 list 把它变成一个列表。整个过程需要 O(len(a)+len(b)) 时间。

请注意，根据您的操作，最好不要使用列表，而只保留 a、b 和 c 表示为计数器.

Answer 3

以下仅使用标准库：

a = ['a', 'b', 'b', 'c', 'c', 'c', 'c', 'd', 'd', 'd', 'e', 'e']
b = ['a', 'c', 'e', 'f','c']
a_set = set(a)
b_set = set(b)

only_in_a = list(a_set - b_set)
diff_list = list()

for _o in only_in_a:
    tmp = a.count(_o) * _o
    diff_list.extend(tmp)

for _b in b_set:
    tmp = (a.count(_b) - b.count(_b)) * _b
    diff_list.extend(tmp)

print diff_list

并给出：

['b', 'b', 'd', 'd', 'd', 'c', 'c', 'e']

符合预期。

Python 列表减法运算关于重复

Python list subtraction operation respecting the repetitions

python

python-2.x

Python 列表减法运算*关于重复*

Python list subtraction operation *respecting the repetitions*

python

python-2.x

Python 列表减法运算关于重复

Python list subtraction operation respecting the repetitions