如何按直接/间接关联对(x,y)元组列表进行分组？

你的问题本质是图的连通分量查找：把每个(x,y)元组视为图的节点，若两个节点共享x值或y值则存在边，最终每个连通分量就是一个关联组。itertools.groupby无法处理这类问题，因为它只能按单一键的连续项分组，无法覆盖链式的间接关联。

实现思路 #

使用**并查集（Union-Find）**数据结构，这是处理连通分量问题的高效方案，尤其适合大型数据集（2067个元组完全无压力）：

• 初始化每个元组为独立集合
• 建立x值到对应元组的映射、y值到对应元组的映射
• 对每个x值下的所有元组，合并为同一集合；对每个y值下的所有元组同理
• 最后将拥有同一根节点的元组归为一组

完整代码 #

class UnionFind:
    def __init__(self, elements):
        self.parent = {elem: elem for elem in elements}
    
    def find(self, x):
        # 路径压缩，加速查找
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 合并两个集合
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root != y_root:
            self.parent[y_root] = x_root

def group_related_tuples(tuples_list):
    if not tuples_list:
        return []
    
    # 初始化并查集
    uf = UnionFind(tuples_list)
    
    # 构建x、y到对应元组的映射
    x_to_tuples = {}
    y_to_tuples = {}
    for t in tuples_list:
        x, y = t
        x_to_tuples.setdefault(x, []).append(t)
        y_to_tuples.setdefault(y, []).append(t)
    
    # 合并同一x下的所有元组
    for tuples in x_to_tuples.values():
        if len(tuples) > 1:
            base = tuples[0]
            for t in tuples[1:]:
                uf.union(base, t)
    
    # 合并同一y下的所有元组
    for tuples in y_to_tuples.values():
        if len(tuples) > 1:
            base = tuples[0]
            for t in tuples[1:]:
                uf.union(base, t)
    
    # 按连通分量分组
    groups = {}
    for t in tuples_list:
        root = uf.find(t)
        groups.setdefault(root, []).append(t)
    
    # 返回分组结果，每个元素是一个关联组的元组列表
    return list(groups.values())

使用示例 #

假设你的元组列表为large_tuple_list，调用方式如下：

result = group_related_tuples(large_tuple_list)
# 遍历结果查看每个分组
for idx, group in enumerate(result, 1):
    print(f"第{idx}组: {group}")

为什么itertools.groupby不适用？ #

groupby要求先按分组键排序，然后仅对连续的同键元素分组，无法处理间接关联的场景。比如元组(a,b)、(b,c)、(c,d)，groupby按x或y分组都无法将三者归为同一组，但并查集可以通过链式合并完成关联。

内容的提问来源于stack exchange，提问作者rodrigo souto