如何基于name的交集高效合并两组由[name, group_id]组成的列表？

• 先将两个输入列表预处理为「分组ID: 组内所有name的集合」的映射结构，方便快速计算任意两个分组的交集大小
• 枚举所有lst1分组和lst2分组的组合，计算交集长度，按交集长度降序排序，优先匹配交集最大的分组对，已匹配的分组不再参与后续匹配，保证每个分组最多只和另一个列表的一个分组合并
• 合并匹配成功的分组的所有name，未匹配到的分组单独保留
• 为所有最终分组统一分配连续的分组ID，最后转换为要求的[name, group_id]格式输出

def merge_groups(lst1, lst2):
    # 预处理：生成分组到name集合的映射
    def build_group_map(lst):
        group_map = {}
        for name, gid in lst:
            group_map.setdefault(gid, set()).add(name)
        return group_map
    
    g1_map = build_group_map(lst1)
    g2_map = build_group_map(lst2)
    
    # 计算所有分组对的交集大小，按从大到小排序
    pairs = []
    for g1_id, g1_names in g1_map.items():
        for g2_id, g2_names in g2_map.items():
            intersect_len = len(g1_names & g2_names)
            if intersect_len > 0:
                pairs.append((-intersect_len, g1_id, g2_id))  # 负号方便升序排序等价于交集降序
    pairs.sort()
    
    used_g1 = set()
    used_g2 = set()
    merged_groups = []
    
    # 优先匹配交集最大的分组对
    for _, g1_id, g2_id in pairs:
        if g1_id not in used_g1 and g2_id not in used_g2:
            merged = g1_map[g1_id] | g2_map[g2_id]
            merged_groups.append(merged)
            used_g1.add(g1_id)
            used_g2.add(g2_id)
    
    # 加入未匹配的g1分组
    for g1_id, g1_names in g1_map.items():
        if g1_id not in used_g1:
            merged_groups.append(g1_names)
    
    # 加入未匹配的g2分组
    for g2_id, g2_names in g2_map.items():
        if g2_id not in used_g2:
            merged_groups.append(g2_names)
    
    # 转换为要求的输出格式
    res = []
    for new_gid, names in enumerate(merged_groups, start=1):
        for name in names:
            res.append([name, new_gid])
    return res

# 测试调用
lst1 = [
    ['apple', 1],
    ['banana', 1],
    ['orange', 1],
    ['123', 2],
    ['456', 2],
    ['abc', 3],
    ['ABC', 3],
    ['tony', 4],
    ['john', 4],
    ['jack', 4],
]

lst2 = [
    ['!@#', 1],
    ['apple', 2],
    ['banana', 2],
    ['strawberry', 2],
    ['lemon', 2],    
    ['john', 3],    
    ['tony', 3],
    ['adella', 3],
]

print(merge_groups(lst1, lst2))

代码输出的分组ID顺序和示例可能略有差异，你可以根据需求调整未匹配分组的加入顺序，即可对齐示例的ID分配规则，核心的分组合并逻辑完全符合需求。

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