我有一个元组列表（每个元组包含2个数字），例如：
array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]
output = [(1, 2, 3, 4), (5, 8, 10)]
我知道可以使用循环和冗余匹配来完成这个任务。但我希望有更好的解决方案，能够在计算上更加轻量级（如果有的话）。
1 2 3 4 5 8 10
(1,2)，则会在某种字典中查找1和2。您搜索它们的祖先（这里没有），然后创建某种合并节点：1 2 3 4 5 8 10
\/
12
1 2 3 4 5 8 10
\/ |
12 /
\/
123
(2,4)、(5,8) 和 (8,10):1 2 3 4 5 8 10
\/ | | \/ |
12 / | 58 /
\/ / \/
123 / 5810
\/
1234
您还需要维护一个“合并头”列表，以便轻松返回元素。
现在我们知道如何构建这样的数据结构了，让我们来实现它。首先，我们定义一个节点：
class Merge:
def __init__(self,value=None,parent=None,subs=()):
self.value = value
self.parent = parent
self.subs = subs
def get_ancestor(self):
cur = self
while cur.parent is not None:
cur = cur.parent
return cur
def __iter__(self):
if self.value is not None:
yield self.value
elif self.subs:
for sub in self.subs:
for val in sub:
yield val
vals = set(x for tup in array for x in tup)
为vals中的每个元素创建一个字典，将其映射到Merge：
dic = {val:Merge(val) for val in vals}
还有 merge_heads：
merge_heads = set(dic.values())
现在对于数组中的每个元组，我们查找相应的祖先Merge对象，我们在其上面创建一个新的Merge，从merge_head集合中删除两个旧的头，并将新的merge添加到其中：
for frm,to in array:
mra = dic[frm].get_ancestor()
mrb = dic[to].get_ancestor()
mr = Merge(subs=(mra,mrb))
mra.parent = mr
mrb.parent = mr
merge_heads.remove(mra)
merge_heads.remove(mrb)
merge_heads.add(mr)
最后，在完成这一步骤后，我们可以简单地为merge_heads中的每个Merge构建一个set:
resulting_sets = [set(merge) for merge in merge_heads]
然后resulting_sets将会是（顺序可能不同）：
[{1, 2, 3, 4}, {8, 10, 5}]
class定义）：vals = set(x for tup in array for x in tup)
dic = {val:Merge(val) for val in vals}
merge_heads = set(dic.values())
for frm,to in array:
mra = dic[frm].get_ancestor()
mrb = dic[to].get_ancestor()
mr = Merge(subs=(mra,mrb))
mra.parent = mr
mrb.parent = mr
merge_heads.remove(mra)
merge_heads.remove(mrb)
merge_heads.add(mr)
resulting_sets = [set(merge) for merge in merge_heads]
这将最坏情况下以O(n2)运行，但您可以使树平衡，使祖先在O(log n)中找到，从而使其变为O(n log n)。此外，您还可以短路祖先列表，使其更快。
(u, v) 时，我们只需通过将一个树的根节点指向另一个树（如果不存在，则创建一个单节点树）来轻松关联两个树 u 和 v。最后，我们只需遍历整个森林以获取结果。from collections import defaultdict
def relation(array):
mapping = {}
def parent(u):
if mapping[u] == u:
return u
mapping[u] = parent(mapping[u])
return mapping[u]
for u, v in array:
if u not in mapping:
mapping[u] = u
if v not in mapping:
mapping[v] = v
mapping[parent(u)] = parent(v)
results = defaultdict(set)
for u in mapping.keys():
results[parent(u)].add(u)
return [tuple(x) for x in results.values()]
mapping[u] 存储节点 u 的祖先（父节点或根节点）。特别地，对于单个节点的树的节点，其祖先是它本身。class Merge:
def __init__(self,value=None,parent=None,subs=None):
self.value = value
self.parent = parent
self.subs = subs
self.root = None
if self.subs:
subs_a,subs_b = self.subs
if subs_a.subs:
subs_a = subs_a.subs
else:
subs_a = [subs_a]
if subs_b.subs:
subs_b = subs_b.subs
else:
subs_b = [subs_b]
self.subs = subs_a+subs_b
for s in self.subs:
s.parent = self
s.root = None
def get_ancestor(self):
cur = self if self.root is None else self.root
while cur.parent is not None:
cur = cur.parent
if cur != self:
self.root = cur
return cur
def __iter__(self):
if self.value is not None:
yield self.value
elif self.subs:
for sub in self.subs:
for val in sub:
yield val
def treeconsolidate(array):
vals = set(x for tup in array for x in tup)
dic = {val:Merge(val) for val in vals}
merge_heads = set(dic.values())
for settomerge in array:
frm = settomerge.pop()
for to in settomerge:
mra = dic[frm].get_ancestor()
mrb = dic[to].get_ancestor()
if mra == mrb:
continue
mr = Merge(subs=[mra,mrb])
merge_heads.remove(mra)
merge_heads.remove(mrb)
merge_heads.add(mr)
resulting_sets = [set(merge) for merge in merge_heads]
return resulting_sets
我认为实现这个的最有效方法将是使用 set，如下：
def transitive_cloure(array):
new_list = [set(array.pop(0))] # initialize first set with value of index `0`
for item in array:
for i, s in enumerate(new_list):
if any(x in s for x in item):
new_list[i] = new_list[i].union(item)
break
else:
new_list.append(set(item))
return new_list
示例运行：
>>> transitive_cloure([(1,2), (1,3), (2,4), (5,8), (8,10)])
[{1, 2, 3, 4}, {8, 10, 5}]
与其他答案的比较（基于Python 3.4）：
这个答案是：6.238126921001822
>>> timeit.timeit("moin()", setup="from __main__ import moin")
6.238126921001822
Willem的解决方案：29.115453064994654 （与类的声明相关的时间被排除在外）
>>> timeit.timeit("willem()", setup="from __main__ import willem")
29.115453064994654
hsfzxjy的解决方案：10.049749890022213
>>> timeit.timeit("hsfzxjy()", setup="from __main__ import hsfzxjy")
10.049749890022213