问个技术问题：

比如： [("a", "b"), ("b", "c"), ("e", "f")]

合并成

[set("a", "b", "c"), set("e, "f")]

（即与有一个元素有交集的，就合并进来）

============= 原列表中有一千个元组，半天没出结果

我写的代码:

#     l = [("a", "b"), ("b", "c"), ("e", "f")]
def merger(l):
out_list = []
for item in l:
temp_set = set(item)
    if len(out_list) == 0:
        out_list.append(temp_set)
    else:
        for item_set in out_list:
            if len(temp_set &amp; item_set) &gt; 0:
                item_set.update(temp_set)
            else:
                out_list.append(temp_set)

Python中如何高效合并元组？求教算法实现

yibo5220 1楼

set(itertools.chain(*arr))

ionicwang 2楼

在Python里合并元组，最直接高效的方法就是直接用 + 运算符或者 * 运算符。

比如，你有两个元组 a 和 b：

a = (1, 2, 3)
b = (4, 5, 6)
merged_tuple = a + b  # 结果是 (1, 2, 3, 4, 5, 6)

或者用 * 来重复元组：

base = (0, 1)
repeated_tuple = base * 3  # 结果是 (0, 1, 0, 1, 0, 1)

如果你有一堆元组放在一个列表里，想合并成一个，用 sum 函数最省事，但记得把起始值设成空元组 ()，不然会报错：

tuple_list = [(1, 2), (3, 4), (5, 6)]
result = sum(tuple_list, ())  # 结果是 (1, 2, 3, 4, 5, 6)

不过要注意，sum 这种方式在元组很多或者很大的时候效率不高，因为每次 + 都会创建新元组。这时候用 itertools.chain 或者列表推导式转成元组会更高效：

import itertools
tuple_list = [(1, 2), (3, 4), (5, 6)]
result = tuple(itertools.chain.from_iterable(tuple_list))  # 结果同上
# 或者用列表推导式
result = tuple(item for tup in tuple_list for item in tup)

总结一下，少量元组合并用 +，大量元组合并用 itertools.chain。

zlyuanteng 3楼

没仔细看题,忽略我写的吧…

itying888 4楼

不确定你程序半天没出结果的原因，但是你的 inner loop 里面不应该再从头遍历 out_list 了，因为前面的元素已经遍历过了，你把 l 里的元素换个顺序，改成[ (“e”, “f”), (“a”, “b”), (“b”, “c”)]再运行试试，肯定有重复的

gougou168 5楼

union find
 from collections import defaultdict class DSU: def __init__(self): self.weights = {} self.parents = {} def find(self, x): if x not in self.parents: self.parents[x] = x self.weights[x] = 1 return x else: path = [x] while self.parents[path[-1]] != path[-1]: path.append(self.parents[path[-1]]) root = path[-1] for node in path: self.parents[node] = root return root def union(self, elements): roots = [self.find(e) for e in elements] heaviest_root = max([(self.weights[root], root) for root in roots])[1] for root in roots: if root != heaviest_root: self.weights[heaviest_root] += self.weights[root] self.parents[root] = heaviest_root def merger(A): """ :type A: List[int] :rtype: int """ dsu = DSU() for a in A: dsu.union(a) d=defaultdict(set) for k,x in dsu.parents.items(): d[x].add(k) return list(d.values())

gougou168 6楼

如果是 [(“a”, “b”), (“b”, “c”), (“c”, “d”)] 呢？全合并成一个？

bupafengyu 7楼

建立一个无向图，然后输出里面所有没有连接在一起的子图就可以了，非常简单的。

h691938207 8楼

你程序死循环的原因应该是这里
 for item_set in out_list: if len(temp_set & item_set) > 0: item_set.update(temp_set) else: out_list.append(temp_set) 
你不断迭代 out_list，然后又不断对它 append，就永远都遍历不完。常见错误了。

gougou168 9楼

ionicwang 10楼

这不是并查集嘛

eggper 11楼

https://gist.github.com/czheo/37710f057af62c4d8933bbb8cad98b7d

h691938207 12楼

并查集。。。

h691938207 13楼

coding=utf-8
# input = [(‘a’, ‘b’), (‘b’, ‘c’), (‘e’, ‘f’)]
# output = [{‘a’, ‘b’, ‘c’}, {‘e’, ‘f’}]

def union_set(items):
ret = []
mark = {}
for item in items:
for n in item:
if n in mark:
for m in item:
ret[mark[n]].add(m)
mark[m] = mark[n]
break
else:
index = len(ret)
s = set()
for n in item:
s.add(n)
mark[n] = index
ret.append(s)

return ret

if name == “main”:
inputs = [(‘a’, ‘b’), (‘b’, ‘c’), (‘a’, ‘e’, ‘f’)]
print(union_set(inputs))

nodeper 14楼

great，代码比较优雅

新学到两个技能：

for-else
集合可用作判断，空集合可当 False