Python 中删除多个列表中的共同元素的最简洁方法

Question

我有n个数字列表。我想确保每个列表都包含特定于该列表的唯一元素。也就是说，没有任何“共享”的重复项跨越任何其他列表。
对于两个列表来说，这很容易做到，但对于n个列表来说则有点棘手。

e.g.   
mylist = [
[1, 2, 3, 4],
[2, 5, 6, 7],
[4, 2, 8, 9]
]

成为：

mylist = [
[1, 3],
[5, 6, 7],
[8, 9]
]

- LittleBobbyTables

---

为什么数字2不在这三个列表中，而数字4仍然出现在第一个列表中？ - Praveen Gollakota

你在意顺序是否被保留吗？ - wim

使用一个包（default_dict）来构建一个“已看到”的列表。用查找匹配的“已看到”生成器替换每个mylist列表（我将其称为sublist），如果找到，则不在最终的sublist中包含它。如果没有找到，则将其添加到包中。 - yurisich

请问 mylist = [[1, 2, 2], [3]] 的预期输出是什么？ - wim

Answer 1

from collections import Counter
from itertools import chain

mylist = [
    [1,2,3,4],
    [2,5,6,7,7],
    [4,2,8,9]
]

counts = Counter(chain(*map(set,mylist)))

[[i for i in sublist if counts[i]==1] for sublist in mylist]
#[[1, 3], [5, 6, 7, 7], [8, 9]]

- dugres

---

这确实很好，但我宁愿不导入Counter和chain，因为这可能会稍微降低运行时间（？）。 - LittleBobbyTables

жҲ‘жӯЈеңЁеҜ»жүҫдёҖз§Қдјҳйӣ…зҡ„ж–№жі•еңЁжҲ‘зҡ„зӯ”жЎҲдёӯжү§иЎҢchain(*mylist)гҖӮйқһеёёеҘҪгҖӮе“Һе‘ҖпјҢжҲ‘з”ҡиҮідёҚйңҖиҰҒеғҸжҲ‘зҡ„зӯ”жЎҲдёӯйӮЈж ·дҪҝз”Ё.get()пјҢеӣ дёәеҪ“然е®ғжҖ»жҳҜиў«е®ҡд№үзҡ„гҖӮжҲ‘еҲ йҷӨдәҶжҲ‘зҡ„зӯ”жЎҲпјҢеӣ дёәдҪ зҡ„зӯ”жЎҲеҮ д№Һе®Ңе…ЁзӣёеҗҢпјҢдҪҶжӣҙеҠ дёҘи°ЁгҖӮ - ninjagecko

@MatthewRNYC：你不应该害怕使用像这个答案建议的基本集合。此外，我看不出chain和Counter构造函数都不是O(N)的任何理由。 - ninjagecko

它不会在一个列表中保留重复项。 - Felix Kling

这是一个很好的解决方案，如果适当的话使用像collections或itertools这样的库是没有问题的。 - wim

@FelixKling：我刚意识到这一点，并修正了dugres的答案。诀窍是只从每个列表中计算数字一次(map(set,mylist)而不是mylist)。 - ninjagecko

Answer 2

这个方法可以在线性时间内完成，需要进行两次遍历。我假设您希望在列表中保留重复项；如果不需要，这个方法可以简化一些：

>>> import collections, itertools
>>> counts = collections.defaultdict(int)
>>> for i in itertools.chain.from_iterable(set(l) for l in mylist):
...     counts[i] += 1
... 
>>> for l in mylist:
...     l[:] = (i for i in l if counts[i] == 1)
... 
>>> mylist
[[1, 3], [5, 6, 7], [8, 9]]

- senderle

Answer 3

由于您不关心顺序，因此可以使用集合减法轻松删除重复项，并将其转换回列表。以下是一个巨大的一行代码：

>>> mylist = [
... [1, 2, 3, 4],
... [2, 5, 6, 7],
... [4, 2, 8, 9]
... ]
>>> mynewlist = [list(set(thislist) - set(element for sublist in mylist for element in sublist if sublist is not thislist)) for thislist in mylist]
>>> mynewlist
[[1, 3], [5, 6, 7], [8, 9]]

注意：这种方法并不是很高效，因为对于每一行都要重新计算重复项。是否存在问题取决于您的数据大小。

- wim

---

没错。我想我应该选择更快的那个 :/ - LittleBobbyTables

是的，这个方法并不高效 - 我会在答案中添加免责声明。但这是个问题吗？在我提出“如何使它更高效？”之前，我总是习惯先问一下，“它需要高效吗？” - wim

@MatthewRNYC “更快”的一个取决于你的数据大小。例如，对于你问题中的数据，这个列表推导式实际上比“计数器”解决方案快大约两倍。 - wim

@wim: 是的，过早优化是不好的。悬停提示显示“此答案无用”，而我也觉得它无用，因为：1）它是一个157个字符的一行代码（并不是说一行代码就不好，但在不到三十秒的时间内无法阅读，而且一行代码应该进行缩进），2）存在一个更简洁优雅的O(N)解决方案，而非O(N^2)的解决方案，3）我看到了一个多余的enumerate，显得粗心。我仍然认为#2理由足以导致投票否决，但现在我发现“is not”部分是有用的，enumerate已被移除，你还考虑了性能问题，所以我撤销了我的投票否决。 - ninjagecko

#2 是支持那个简单而优雅的解决方案的原因。这并不是在 StackOverflow 上给其他解决方案打负分的理由，这会扼杀创造力。当然，我可以像这样将其转换为不到80个字符的一行：l=[list(set(t) - set(x for s in m for x in s if s is not t)) for t in m]，但它可能不太容易自我说明如何使用列表推导式。:)不确定您所说的缩进单行代码是什么意思。 - wim

Answer 4

使用set()是正确的方法，虽然你不一定要使用列表推导。

无需额外导入：

mylist = [
[1, 2, 3, 4],
[2, 5, 6, 7],
[4, 2, 8, 9]
]
>>> result_list = []
>>> for test_list in mylist:
...     result_set = set(test_list)
...     for compare_list in mylist:
...         if test_list != compare_list:
...             result_set = result_set - set(compare_list)
...     result_list.append(result_set)
...
>>> result_list
[set([1, 3]), set([5, 6, 7]), set([8, 9])]

- monkut

Answer 5

这是我的解决方案，使用 Counter 构建所有共同数字的集合，然后执行一个集合差异操作：

from collections import Counter

def disjoin(lsts):
    c = Counter(num for lst in lsts for num in lst)
    common = set(x for x,v in c.items() if v > 1)
    result = []
    for lst in lsts:
        result.append(set(lst) - common)
    return result

例子：

>>> remove_common(mylist)
[set([1, 3]), set([5, 6, 7]), set([8, 9])]

- Rik Poggi