Python 多集合重叠元素与所属来源集合的映射实现方法

你完全不需要暴力枚举所有集合的两两/多组合求交集，要解决这个问题的核心思路和交集计算的方向是反过来的：我们不需要顺着集合找重叠的元素，只需要顺着每个元素反向记录它的来源集合，就能一次性得到所有映射关系。

你想到用Counter的思路方向完全正确——Counter的本质就是线性遍历所有元素，统计每个元素的出现次数。而我们要做的实现，本质上就是把Counter里“计数累加”的逻辑，替换成“追加来源集合到列表”，比Counter的输出粒度更细，不仅能知道每个元素出现在几个集合里，还能拿到具体的来源列表。

具体实现流程 #

1. 先把所有待统计的集合统一整理到一个可迭代的列表里，后续不需要单独操作每个集合：

   all_sets = [s1, s2, s3, s4, s5, s6]
   

2. 初始化一个带空列表默认值的字典，用来存元素到来源集合的映射关系：

   from collections import defaultdict
   
   element_source_map = defaultdict(list)
   # 线性遍历每个集合、每个元素，一次遍历完成所有映射
   for set_item in all_sets:
       for elem in set_item:
           element_source_map[elem].append(set_item)
   

3. 直接拿到的element_source_map就已经和你期望的输出结构完全一致：每个键是集合里出现的元素，对应的值就是持有这个元素的所有来源集合的列表，比如"a": [s1, s2, s3]、"x": [s4, s5]、"u": [s6]，和你给出的示例结构没有差异。

可选的过滤逻辑 #

你提到需求是“统计所有重叠元素”，如果只需要保留至少出现在2个集合以上的重叠元素，过滤掉仅在单个集合里出现的孤立元素，只需要加一行字典推导式做筛选即可：

# 仅保留来源集合数量≥2的元素
result = {
    elem: sources 
    for elem, sources in element_source_map.items() 
    if len(sources) >= 2
}

你给出的示例输出里包含了仅属于s6的元素u，说明示例只是用来演示字典的结构，并非真的要过滤单来源元素，实际使用时可以根据需求决定是否加这层过滤。

两种实现思路的效率对比 #

• 如果走两两集合求交集的路线，n个集合需要计算n*(n-1)/2次交集，整体时间复杂度随集合数量呈平方级上涨，算完交集还要对重复出现的元素做去重、整理来源列表，冗余操作非常多
• 反向元素索引的路线，整体计算量等于所有集合的元素总个数，是线性时间复杂度，一次遍历就能拿到完整的映射关系，没有任何冗余计算

你之前接触的intersect方法，本质是找“同时存在于指定的全部集合里的公共元素”，方向和我们现在要解决的“遍历找每个元素对应的所有来源集合”的问题完全不匹配，所以会觉得用不上。

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