我有一个元组列表（每个元组由 2 个数字组成），例如：
array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]
可以说，这些数字是一些 db 对象（记录）的 id，在一个元组中，有重复对象的 id。这意味着 1 和 2 是重复的。1 和 3 是重复的，这意味着 2 和 3 也是重复的。
如果 a == b 和 b == c 那么 a == c
现在我想将所有这些重复的对象 id 合并到一个元组中，如下所示：
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,3)，因此我们查找1( 12) 和3( 3) 的祖先并执行另一个合并：
1 2 3 4 5 8 10
\/ |
12 /
\/
123
接下来我们合并(2,4)and(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并为映射到 a的每个元素创建一个字典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)
最后，在我们完成之后，我们可以简单地set为每个Mergein构造一个merge_heads：
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(n 2 )中运行最坏的情况，但您可以平衡树，以便在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（父或根）。特别地，单节点树的节点的祖先是它自己。
请参阅我对 Moinuddin 答案的评论：这个已接受的答案不验证您可以在http://rosettacode.org/wiki/Set_consolidation#Python找到的测试。不过我没有挖出来。
根据威廉的回答，我会提出一个新的提议。这个命题的问题是 get_ancestor 调用中的递归性：为什么每次我们被问到我们的祖先时我们应该爬上树，当我们只记得找到的最后一个根时（并且仍然从那个点向上爬，以防它改变） . 事实上，Willem 的算法不是线性的（类似于 nlogn 或 n²），而我们可以很容易地消除这种非线性。
另一个问题来自迭代器：如果树太深（我在用例中遇到了问题），你会在迭代器中得到一个 Python 异常（递归过多）。因此，我们应该合并子叶子，而不是构建一棵完整的树（而不是有 2 个叶子的分支，我们构建有 N 个叶子的分支）。
我的代码版本如下：
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
在小型合并中，这不会改变很多事情，但我的经验表明，在包含许多元素的大量集合中爬上树可能会花费很多：在我的情况下，我必须处理 100k 集合，每个集合包含 2 到 1000元素，每个元素可能出现在 1 到 1000 个集合中......
我认为实现这一目标的最有效方法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
威廉的解决方案：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