如何对字符串分组列表按前三元素匹配实现无重复高效分组

你原来的代码是O(n²)的时间复杂度，百万级数据量下完全无法运行，且没有做分组去重，我们可以通过倒排索引+集合运算优化到近线性复杂度。

实现思路 #

• 预构建倒排索引：记录每个字符串元素出现在哪些子列表中，后续求包含指定三个元素的子列表时，直接取对应索引集合的交集即可，无需遍历全量列表
• 基准键无需考虑顺序，集合交集运算会自动匹配所有包含三个元素的子列表
• 分组去重：将每个分组的索引排序后转成不可变的元组，存入set自动去重，完美解决顺序不同内容相同的分组重复问题

代码实现 #

from collections import defaultdict

def group_text_list(text_list):
    # 1. 构建倒排索引：key是元素，value是包含该元素的子列表索引集合
    elem_index = defaultdict(set)
    for idx, sub_list in enumerate(text_list):
        for elem in sub_list:
            elem_index[elem].add(idx)
    
    unique_groups = set()
    # 2. 遍历每个子列表的前3个元素作为基准
    for idx, sub_list in enumerate(text_list):
        key_elems = sub_list[:3]
        # 取三个元素对应的索引集合的交集，就是所有符合条件的子列表索引
        try:
            match_indexes = set.intersection(*[elem_index[e] for e in key_elems])
        except KeyError:
            continue
        # 过滤只有自身的分组，和你原有代码逻辑保持一致
        if len(match_indexes) < 2:
            continue
        # 排序后转元组，方便去重
        sorted_group = tuple(sorted(match_indexes))
        unique_groups.add(sorted_group)
    
    # 3. 转成列表格式输出
    return [list(group) for group in unique_groups]

# 测试示例数据
text_list = [['aaa','bbb','ccc','ddd','eee'],
['fff','ggg','hhh','iii','jjj'],
['xxx','mmm','ccc','bbb','aaa'],
['fff','xxx','aaa','bbb','ddd'],
['aaa','bbb','ccc','ddd','eee'],
['fff','xxx','aaa','ddd','eee'],
['iii','xxx','ggg','jjj','aaa']]

print(group_text_list(text_list))
# 输出：[[0, 2, 4], [3, 5]]，和预期完全一致

性能说明 #

• 倒排索引构建时间复杂度为O(n)，n是子列表总数
• 每个基准的匹配通过集合交集完成，远快于遍历全量列表，百万级数据量下可在几秒内完成计算
• 自动完成分组去重，无需额外处理

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