从元组列表中提取唯一值及其关联配对的实现方法

我有如下格式的元组列表：

[
    ('a', 'AA'), # pair 1

    ('d', 'AA'), # pair 2
    ('d', 'a'),  # pair 3
    ('d', 'EE'), # pair 4

    ('b', 'BB'), # pair 5
    ('b', 'CC'), # pair 6
    ('b', 'DD'), # pair 7

    ('c', 'BB'), # pair 8
    ('c', 'CC'), # pair 9
    ('c', 'DD'), # pair 10

    ('c', 'b'),  # pair 11

    ('d', 'FF'), # pair 12

]

列表中的每个元组代表一组相似（或重复）的项对。我需要生成一个字典，其中键为元组中的某个唯一项，值为该键所有关联项组成的列表。例如：

• 'a'与'AA'相似（配对1），'AA'又与'd'相似（配对2），'d'还与'EE'、'FF'相似（配对4、12），因此'a'对应的关联列表是['AA', 'd', 'EE', 'FF']
• 'b'与'BB'、'CC'、'DD'相似（配对5-7），'c'又与这些项及'b'相似（配对8-11），因此'b'对应的关联列表是['BB', 'CC', 'DD', 'c']

预期输出示例：

{'a':['AA', 'd', 'EE', 'FF'], 'b':['BB', 'CC', 'DD', 'c']}

根据元组关系，['a', 'AA', 'd', 'EE', 'FF']属于同一相似组，组内任意项均可作为键，其余项为对应值，输出也可为：

{'AA':['a', 'd', 'EE', 'FF'], 'c':['BB', 'CC', 'DD', 'b']}

请问如何处理包含数千个此类元组的列表？

处理这类连通分量分组问题，最适合的算法是并查集（Union-Find），它的时间复杂度接近O(n)，处理数千个元组完全没问题。具体步骤如下：

1. 实现并查集数据结构 #

并查集主要包含两个核心操作：

• find：查找某个元素的根节点（代表整个连通组）
• union：将两个元素所在的连通组合并

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    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):
        # 先确保两个元素都在父字典中
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        # 找到各自的根节点
        root_x = self.find(x)
        root_y = self.find(y)
        # 如果根不同，合并
        if root_x != root_y:
            self.parent[root_y] = root_x

2. 遍历元组列表，构建连通关系 #

把所有元组中的元素都加入并查集，完成分组：

pairs = [
    ('a', 'AA'),
    ('d', 'AA'),
    ('d', 'a'),
    ('d', 'EE'),
    ('b', 'BB'),
    ('b', 'CC'),
    ('b', 'DD'),
    ('c', 'BB'),
    ('c', 'CC'),
    ('c', 'DD'),
    ('c', 'b'),
    ('d', 'FF'),
]

uf = UnionFind()
for x, y in pairs:
    uf.union(x, y)

3. 生成目标字典 #

先把每个连通组的元素整理到一起，再为每个组选一个代表作为键，其余元素作为值：

# 第一步：按根节点分组
groups = {}
for item in uf.parent:
    root = uf.find(item)
    if root not in groups:
        groups[root] = []
    groups[root].append(item)

# 第二步：生成目标字典
result = {}
for root, members in groups.items():
    # 去掉根节点本身，剩下的就是关联项
    result[root] = [m for m in members if m != root]

print(result)

运行后输出示例（取决于根节点的选择，结果符合要求即可）：

{'a': ['AA', 'd', 'EE', 'FF'], 'b': ['BB', 'CC', 'DD', 'c']}

如果想让每个组的任意元素都能作为键，可以扩展为：

full_result = {}
for members in groups.values():
    for key in members:
        full_result[key] = [m for m in members if m != key]

print(full_result['AA'])  # 输出: ['a', 'd', 'EE', 'FF']

内容的提问来源于stack exchange，提问作者Naveen Reddy Marthala