求教 Python 合并元组算法

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

out_list

temp_set

item_set

元组

13 条回复 2018-12-13 11:34:05 +08:00

doraemon1293

2018-12-12 18:17:10 +08:00

set(itertools.chain(*arr))

doraemon1293

2018-12-12 18:18:25 +08:00

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

sikariba

2018-12-12 18:23:17 +08:00

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

doraemon1293

2018-12-12 18:24:19 +08:00

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

2018-12-12 18:29:29 +08:00

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

1nakaELYBbsXbZxY

2018-12-12 18:30:12 +08:00

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

sikariba

2018-12-12 18:38:54 +08:00

你程序死循环的原因应该是这里
```
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

2018-12-12 19:04:02 +08:00

ihciah

2018-12-12 19:11:02 +08:00

这不是并查集嘛

aijam

2018-12-12 19:27:00 +08:00

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

mskf

2018-12-12 20:44:41 +08:00

并查集。。。

hustlibraco

2018-12-12 22:42:46 +08:00

# 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

2018-12-13 11:34:05 +08:00

@aijam great，代码比较优雅

新学到两个技能：

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