Python中多个集合的并集

Question

[[1, '34', '44'], [1, '40', '30', '41'], [1, '41', '40', '42'], [1, '42', '41', '43'], [1, '43', '42', '44'], [1, '44', '34', '43']]

我有一个列表的列表。我的目标是检查任何一个子列表是否与其他子列表（不包括第一个索引对象）有任何共同点。如果有任何共同点，则合并这些子列表。

例如，对于这个示例，我的最终答案应该是类似于：

[[1, '34', '44', '40' '30', '41', '42', '43']]

我理解我应该将子列表转换为集合，然后使用union()和intersection()操作。但是我卡在了如何比较每个集合/子列表上。我无法运行循环并逐个比较每个子列表，因为列表的内容会被修改，这会导致错误。

我想知道是否有一种有效的方法来比较所有子列表（转换为集合），并获取它们的并集？

- Tapojyoti Mandal

---

您需要相同的顺序吗？ - Ajay

不需要保持顺序。 - Tapojyoti Mandal

你需要这个吗？https://dev59.com/G4bca4cB1Zd3GeqPYafQ#27803361 - Mazdak

实际上，我忘记强调一个重要条件了。对我的错误感到抱歉。我也提到过，子列表只有在它们有共同之处时才应该被合并，否则它们应该保持原样。所以，首先需要检查intersection()，如果不为空，那么只有union才能执行。@Peter Wood 不，不会有任何具有单独起始索引元素（如'2'或'3'）的子列表。我的意思是，在列表的所有子列表中，所有子列表都具有相同的第一个索引元素。 - Tapojyoti Mandal

@TapojyotiMandal 欢迎！;) - Mazdak

Answer 1

itertools模块可以轻松解决这个问题：

>>> from itertools import chain
>>> list(set(chain.from_iterable(d)))
[1, '41', '42', '43', '40', '34', '30', '44']

另一种方法是将列表解包为单独的参数传递给union()函数：

>>> list(set().union(*d))
[1, '41', '42', '43', '40', '34', '30', '44']

后者的方法可以消除所有重复项，而且不需要先将输入转换为集合。此外，它也不需要进行导入操作。

- Raymond Hettinger

---

itertools通常如何扩展？根据您的经验，这种操作能否处理数千万或数亿个项目的长列表（这里的“项目”是字符串）？甚至更大？ - Hassan Baig

"chain.from_iterable()" 步骤在规模上是不变的。其整个状态在任何时候都仅存储在指向两个迭代器的指针中。而"set()"和"list()"部分的内存使用量与总唯一输入数量成比例增加。在我的64位机器上，一亿个唯一输入需要4.3 GB RAM用于set对象和0.9 GB RAM用于list对象。 - Raymond Hettinger

最好写成set.union()，因为set()初始化为空集。在这种情况下没问题，但是我曾经花了很多时间寻找错误，因为我假设这个操作可以推广到交集。使用set.既可以进行并集操作也可以进行交集操作! - Radio Controlled

@RadioControlled: set().union(*d)可以处理空的d，这比与交集所做的对称性更重要。 - user2357112

很遗憾，所有的答案都回答了一个与问题所问不同的问题，这可能是由于问题中示例的选择不佳造成的。实际上，该问题似乎要求更接近超图连通分量算法的东西，而不仅仅是将所有内容倒入单个集合中。（dermen的答案略有不同，但最终结果甚至更加错误。） - user2357112

Answer 2

使用解包操作符*：

>> list(set().union(*a))
[1, '44', '30', '42', '43', '40', '41', '34']

感谢Raymond Hettinger和ShadowRanger的评论！

请注意，

set.union(*tup)

将解压缩为

set.union(tup[0], tup[1], ... tup[n - 1])

)

- Ami Tavory

---

这个方法运行得很好，谢谢。能否解释一下代码中 '*' 的用途？或者提供一个相关的链接让我能够学习并且更好地理解。 - Tapojyoti Mandal

就翻译而言，FWIW，“tuple”步骤没有效果，因为星号解包适用于任何可迭代对象。您还可以使用“map(set, a)”替换列表推导式。结果归结为“list(set.union(*map(set, a)))”。 - Raymond Hettinger

@TapojyotiMandal 请查看答案中的解释。 - Ami Tavory

如果您将set.union(*map(set, a))改为set().union(*a)，则可以显著减少临时set的数量。之所以需要使用map(set，)是因为您调用set.union，第一个参数成为其被调用的“self”，但是如果您以空set为基础，则union接受其余参数的任意可迭代对象。请注意，这样做不会改变原始含义。 - ShadowRanger

Answer 3

>>> big = [[1, '34', '44'], [1, '40', '30', '41'], [1, '41', '40', '42'], [1, '42', '41', '43'], [1, '43', '42', '44'], [1, '44', '34', '43']]
>>> set(reduce ( lambda l,a : l + a, big))
set([1, '44', '30', '42', '43', '40', '41', '34'])

如果您真的想要一个嵌套列表作为最终结果

>>>>[list(set(reduce ( lambda l,a : l + a, big)))]
[[1, '44', '30', '42', '43', '40', '41', '34']]

如果您不喜欢重新编写一个lambda函数来进行列表添加：

>>>>[list(set(reduce ( list.__add__, big)))]
[[1, '44', '30', '42', '43', '40', '41', '34']]

编辑：在您建议使用itertools.chain而不是list.__add__之后，我对两者进行了timeit测试，并使用原始帖子的原始变量。

看起来timeit计时list.__add__约为2.8秒，而itertools.chain约为3.5秒。

我在这个页面上进行了检查，是的，您关于itertools.chain包含from_iterable方法可提供巨大的性能提升的建议是正确的。请参见下面的list.__add__，itertools.chain和itertools.chain.from_iterable。

>>> timeit.timeit("[list(set(reduce ( list.__add__, big)))]", setup="big = [ [10,20,30,40] for ele in range(10000)]", number=30)
16.051744650801993
>>> timeit.timeit("[list(set(reduce ( itertools.chain, big)))]", setup="big = [ [10,20,30,40] for ele in range(10000)]", number=30)
54.721315866467194
>>> timeit.timeit("list(set(itertools.chain.from_iterable(big)))", setup="big = [ [10,20,30,40] for ele in range(10000)]", number=30)
0.040056066849501804

非常感谢您的建议 :)

- Azurtree

---

将列表按此方式相加是一种效率低下的 O(n**2) 操作，几乎总是不明智的选择。请改用 "itertools.chain"。 - Raymond Hettinger

Answer 4

In [20]: s
Out[20]: 
[[1, '34', '44'],
 [1, '40', '30', '41'],
 [1, '41', '40', '42'],
 [1, '42', '41', '43'],
 [1, '43', '42', '44'],
 [1, '44', '34', '43']]
In [31]: list({x for _list in s for x in _list})
Out[31]: [1, '44', '30', '42', '43', '40', '41', '34']

更新：

感谢您的评论。

- Ajay

---

你不需要使用列表推导式，因为集合构造器可以接受一个生成器。 - Peter Wood

@PeterWood OP要求列出一个清单作为他的最终答案。 - Ajay

不需要理解，它已经传递给了“set”。 - Peter Wood

用集合推导式替换列表推导式，可以将其简化为一个漂亮、干净的答案：list({x for _list in s for x in _list})。 - Raymond Hettinger

Answer 5

你可以使用itertools来执行此操作。假设你的列表名为A。

import itertools

single_list_with_all_values = list(itertools.chain(*A))
single_list_with_all_values.sort()

print set(single_list_with_all_values)

- Arpit Goyal

---

这很不错。但是还有一些改进的空间。1）应该始终将 chain(*it) 更改为 chain.from_iterable(it)。2）因为制作 set 时顺序会丢失，所以没有必要进行 sort()。3）没有排序，制作 set 之前也不需要转换为 list。通过这些更改，可以简化为 set(chain.from_iterable(d))。 - Raymond Hettinger

Answer 6

from functools import reduce

out = list(reduce(set.union, iterable))

只要iterable的第一个元素是集合，就可以使用此函数。否则，不行。

out = list(reduce(set.union, iterable[1:], set(iterable[0])))

- PeterFoster

Answer 7

仅使用Python 2测试：我个人喜欢reduce的可读性，再加上一个简单的条件函数，例如：

# PYTHON 2 ONLY!
somelists = [[1, '41', '40', '42'], [1, '42', '41', '43'], [1, '43', '42', '44'], [1, '44', '34', '43']] # your original lists
somesets = map(set,somelists) #your lists as sets

def condition(s1,s2): # condition to apply recursively to the sets
    if s1.intersection(s2):
        return s1.union(s2)
reduce( condition,somesets)
#{1, '30', '34', '40', '41', '42', '43', '44'}

如果您想要，当然可以将此结果转换为2D列表 list([reduce(...

我要注意的是，这比chain.fromiterable答案慢大约3倍。

- dermen