如何在计算互补列表时正确处理重复项？

Question

虽然这个问题似乎与之前的问题有关（比如这个：Python, compute list difference），但并不完全相同，即使是包含两个建议的最佳评分答案也不会完全回答以下问题一.

我有一个主（无序）列表 L 包含重复的值；以整数列表为例：

L = [3, 1, 4, 1, 5, 9, 2, 6, 5]

我有一个较小的列表，其中包含从 L 中选择的值，例如：

x = [4, 1, 3]

x 中元素的顺序与 L 中元素的顺序没有任何关系。

现在，我想计算差异 L-x 的方式是连接 x 并且这个差异会给出与 L 相同的列表（顺序除外） ;更准确地说：

list(sorted(x + D(L,x))) == list(sorted(L))

第一个坏主意显然是使用集合，因为重复的不会被正确处理。

第二个坏主意是使用一些带有过滤器的列表理解，例如：

[ e for e in L if e not in x ]

因为我的示例中的值 1 将被丢弃，尽管该值的一个实例应该出现在预期的差异中。

据我所知，最有效的方法是对两个列表进行排序，然后对两个列表进行迭代（迭代器可能会有所帮助）并仔细考虑重复项；这将是一个 O(n log n) 解决方案。

我不追求速度；我想知道一些简洁的 pythonic 语法是否可以做到这一点；如果它可以在一两行中完成预期的任务，即使 O(n²) 或更糟也是可以接受的。

Answer 1

您需要 collections.Counter 提供的多重集操作：

>>> L = [3, 1, 4, 1, 5, 9, 2, 6, 5]
>>> x = [4, 1, 3]
>>> list((Counter(L) - Counter(x)).elements())
[1, 5, 5, 9, 2, 6]

这是 O(n)。如果需要，您还可以使用 OrderedCounter 保留顺序并维护 O(n)。

from collections import Counter, OrderedDict

class OrderedCounter(Counter, OrderedDict): 
    pass

Answer 2

您可能会争辩说此任务的代码太多，但它保留了原始列表的顺序。

    L = [3, 1, 4, 1, 5, 9, 2, 6, 5]
    x = [4, 1, 3]

    temp = x[:]
    diff = []
    for i in L:
        if i in temp:
            temp.pop(temp.index(i))
            continue
        diff.append(i)
    print(diff)  # -> [1, 5, 9, 2, 6, 5]

Answer 3

似乎很好用 collections.Counter:

>>> from collections import Counter
>>> 
>>> d = Counter(L) - Counter(x)
>>> list(d.elements())
[1, 5, 5, 9, 2, 6]

如何在计算互补列表时正确处理重复项？

How to correctly handle duplicates in computing the complementary list?

python

list

set-difference