如何高效对仅单点位不同的点分隔字符串列表进行分组

输入是一组由点号拼接的字符串，所有字符串按点拆分后得到的变量段数量完全一致。需要将仅在同一个点位存在1个变量差异的字符串归为同一分组，要求：

• 每个字符串仅归属一个分组，不可跨组重复
• 变量点位最多20个，输入字符串数量较大，需保证算法性能

示例输入：
['A.B.C.D','A.A.C.D','A.B.E.F','A.B.E.GG']

示例输出：

['A.B.C.D','A.A.C.D']
['A.B.E.F','A.B.E.GG']

你原有使用itertools.groupby的方案失效主要有两个原因：

1. itertools.groupby只会把连续出现、键值相同的元素聚为一组，不会对全局所有元素做聚类
2. 你用相邻元素对比的逻辑计算差异，无法覆盖全局所有相似元素，也无法处理重复、乱序的输入

我们采用掩码特征分组的思路，时间复杂度为O(M*N)（M为输入字符串数量，N为变量点位数量，最高20），完全适合大数据量场景：

1. 对每个字符串，生成N个掩码特征：将第i个点位替换为统一通配符，保留其他点位不变
2. 所有共享同一个掩码特征的字符串，必然仅在第i个点位存在差异，符合分组要求
3. 标记已分配分组的字符串，避免重复入组

from collections import defaultdict

def group_strings(input_list):
    # 获取变量点位数量
    dim_count = len(input_list[0].split('.'))
    # 构建掩码特征映射表
    mask_map = defaultdict(list)
    for s in input_list:
        dims = s.split('.')
        for i in range(dim_count):
            # 生成第i位的掩码特征
            mask_dims = dims.copy()
            mask_dims[i] = '*'
            mask_key = '.'.join(mask_dims)
            mask_map[mask_key].append(s)
    # 筛选有效分组，避免重复分配
    used = set()
    groups = []
    # 优先处理元素多的分组，避免小分组先占用公共元素
    for mask_key in sorted(mask_map.keys(), key=lambda k: len(mask_map[k]), reverse=True):
        candidate = mask_map[mask_key]
        valid = [s for s in candidate if s not in used]
        if len(valid) >= 2:
            groups.append(valid)
            used.update(valid)
    # 若需要将未分组的单个元素也作为独立分组返回，可取消注释下行代码
    # groups.extend([[s] for s in input_list if s not in used])
    return groups

基础示例测试 #

test1 = ['A.B.C.D','A.A.C.D','A.B.E.F','A.B.E.GG']
print(group_strings(test1))
# 输出：[['A.B.C.D', 'A.A.C.D'], ['A.B.E.F', 'A.B.E.GG']]

补充示例测试 #

运行你提供的补充输入，输出分组为：

[
  ['D.1.2.A.1.B.C', 'D.7.2.A.1.B.C', 'D.21.2.A.1.B.C', 'D.8.2.A.1.B.C', 'D.10.2.A.1.B.C', 'D.14.2.A.1.B.C', 'D.15.2.A.1.B.C', 'D.16.2.A.1.B.C', 'D.17.2.A.1.B.C', 'D.18.2.A.1.B.C', 'D.19.2.A.1.B.C', 'D.20.2.A.1.B.C', 'D.22.2.A.1.B.C', 'D.23.2.A.1.B.C', 'D.25.2.A.1.B.C', 'D.26.2.A.1.B.C', 'D.27.2.A.1.B.C'],
  ['D.15.6.A.1.B.C', 'D.25.6.A.1.B.C', 'D.8.6.A.1.B.C']
]

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