我有一个元组列表（每个元组由 2 个数字组成），例如：

array = [(1, 2), (1, 3), (2, 4), (5, 8), (8, 10)]

可以说，这些数字是一些数据库对象（记录）的 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 and 2在某种字典中。你搜索他们的祖先（这里没有），然后你创建某种合并节点:

1  2  3  4  5  8  10
 \/
 12

接下来我们合并(1,3)所以我们查找祖先1 (12) and 3 (3) 并执行另一次合并：

1  2  3  4  5  8  10
 \/   |
 12  /
   \/
  123

接下来我们合并(2,4) and (5,8) and (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}

and the merge_heads:

merge_heads = set(dic.values())

现在对于数组中的每个元组，我们查找相应的Merge对象是祖先，我们创建一个新的Merge最重要的是，从上面取下两个旧头merge_head设置并添加新的merge to it:

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对于每个Merge in merge_heads:

resulting_sets = [set(merge) for merge in merge_heads]

and 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]

This will worst case run in O(n²), but you can balance the tree such that the ancestor is found in O(log n) instead, making it O(n log n). Furthermore you can short-circuit the list of ancestors, making it even faster.