如何编写高效Python3函数合并两个集合列表生成交集划分

现有两个集合列表，二者均为同一全集的划分（列表内各集合无重复元素，且两个列表包含的所有元素完全相同）。例如：
[{1, 2, 3}, {4, 5}, {6, 7}] 和 [{1, 2}, {3, 4}, {5, 6, 7}]

需要编写Python3函数mergeSets，将这两个集合列表合并，输出新的集合列表，其中每个集合由同时存在于两个输入集合分组中的元素组成（即取两个输入集合的非空交集）。由于需处理大规模集合，函数需尽可能高效。

补充说明：

• 数据无需排序，元素类型可为非整数
• 输入列表无需排序，集合顺序可随机

示例代码及预期运行效果：

def mergeSets(x, y):
    out = set()
    for i in x:
        out = out.union(i)
        # 这能让我得到所有元素的集合，但思路卡在这里了
        # 问题听起来简单，但想了几小时也想不出好算法 :(
        # 我找到了set.intersection()函数，但它只适用于单个集合，不适用于集合列表
    return out


x = mergeSets([{1, 2, 3}, {4, 5}, {6, 7}], [{1, 2}, {3, 4}, {5, 6, 7}])
print(x)
# 预期输出: [{1, 2}, {3}, {4}, {5}, {6, 7}]
x = mergeSets([{1, 2}, {3, 4, 5, 6, 7}, {8}], [{1}, {2, 3, 4}, {5, 6, 7, 8}])
print(x)
# 预期输出: [{1}, {2}, {3, 4}, {5, 6, 7}, {8}]

核心思路 #

要高效处理大规模集合，关键是通过元素的分组标识来归类：

1. 给第一个列表里的每个元素标记它所属的集合索引
2. 给第二个列表里的每个元素标记它所属的集合索引
3. 将拥有相同双索引组合的元素归为一组，每组就是两个输入集合的非空交集

这种方法的时间复杂度为O(N)（N是元素总数），远优于暴力遍历所有集合对求交集的O(M*K)（M、K为两个列表的集合数量），适合大规模数据场景。

实现代码 #

def mergeSets(x, y):
    # 建立元素到x中集合索引的映射
    elem_x_map = {}
    for idx, s in enumerate(x):
        for elem in s:
            elem_x_map[elem] = idx
    
    # 按(x索引, y索引)的组合分组元素
    groups = {}
    for idx, s in enumerate(y):
        for elem in s:
            key = (elem_x_map[elem], idx)
            groups.setdefault(key, set()).add(elem)
    
    # 将分组转换为列表返回
    return list(groups.values())

测试验证 #

运行示例测试用例：

# 测试用例1
result1 = mergeSets([{1, 2, 3}, {4, 5}, {6, 7}], [{1, 2}, {3, 4}, {5, 6, 7}])
print(result1)
# 输出（顺序可能不同）: [{1, 2}, {3}, {4}, {5}, {6, 7}]

# 测试用例2
result2 = mergeSets([{1, 2}, {3, 4, 5, 6, 7}, {8}], [{1}, {2, 3, 4}, {5, 6, 7, 8}])
print(result2)
# 输出（顺序可能不同）: [{1}, {2}, {3, 4}, {5, 6, 7}, {8}]

额外说明 #

• 支持任意可哈希类型的元素（如字符串、元组等），符合题目要求
• 输出集合的顺序不固定，但每组元素准确，满足题目对顺序无要求的条件
• 两次线性遍历完成所有操作，避免了大量集合交集运算，性能高效

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