Python生成与原字符串差异指定字符数的字符串列表最优方法

这个问题我之前也碰到过，暴力迭代多次确实容易产生重复结果还低效，其实用组合+笛卡尔积的思路就能一次性生成所有符合要求的字符串，完全不用多次循环~

暴力法的问题在于会重复生成中间结果，还存在冗余计算。更高效的方式是拆解成两步：

• 第一步：先选出所有需要修改的X个位置的组合（比如原字符串长度为3、X=2时，位置组合就是(0,1)、(0,2)、(1,2)）
• 第二步：对每个位置组合，为每个要修改的位置生成合法的替换字符（ACGT中不等于原位置字符的选项），再用笛卡尔积生成所有可能的替换组合，最后拼接成完整字符串。

这种方式直接生成最终结果，没有中间冗余，时间复杂度是C(n,X)*3^X（n为原字符串长度），这是理论上的最优复杂度——毕竟符合要求的字符串总数就是这么多。

先导入需要的工具库：

import itertools

核心函数实现：

def generate_hamming_strings(original, x, chars='ACGT'):
    n = len(original)
    if x < 0 or x >= n:
        raise ValueError("X必须是小于字符串长度的非负整数")
    
    result = []
    # 生成所有要修改的X个位置的组合（避免重复排列）
    for positions in itertools.combinations(range(n), x):
        # 为每个要修改的位置生成替换选项（排除原字符，保证差异数为X）
        replacements = []
        for pos in positions:
            original_char = original[pos]
            opts = [c for c in chars if c != original_char]
            replacements.append(opts)
        
        # 生成所有替换组合的笛卡尔积
        for replacement_tuple in itertools.product(*replacements):
            s_list = list(original)
            # 替换对应位置的字符
            for idx, pos in enumerate(positions):
                s_list[pos] = replacement_tuple[idx]
            result.append(''.join(s_list))
    
    return result

以原字符串'AGT'、X=2为例：

original = 'AGT'
x = 2
output = generate_hamming_strings(original, x)
print(output)

输出会包含所有恰好2个字符与原字符串不同的ACGT组合，比如'AAT'、'ACT'、'CGT'、'AGA'等，总共C(3,2)*3^2 = 27个结果，完全符合需求。

如果你的需求是修改X个位置但允许替换后字符与原字符相同（即最终差异数可能小于X），只需要把替换选项改成opts = list(chars)即可，此时结果数量为C(n,X)*4^X。

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