求教 Python 合并元组算法

[zealinux]

问个技术问题：

比如： [("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 & item_set) > 0:
                    item_set.update(temp_set)
                else:
                    out_list.append(temp_set)

[doraemon1293]

set(itertools.chain(*arr))

[doraemon1293]

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

[sikariba]

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

[doraemon1293]

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())
```

[Jex]

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

[1nakaELYBbsXbZxY]

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

[sikariba]

你程序死循环的原因应该是这里
```
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，就永远都遍历不完。常见错误了。

[rabbbit]

[ihciah]

这不是并查集嘛

[aijam]

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

[mskf]

并查集。。。

[hustlibraco]

# 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))

[zealinux]

@aijam great，代码比较优雅

新学到两个技能：

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