python - 如何使用 d-mismatches，python 生成所有字符串

Question

我有一个以下字符串 - “AACCGGTTT”（字母是 [“A”，“G”，“C”，“T”]）。我想在任何两个位置生成与原始字符串不同的所有字符串，即

GAGCGGTTT
^ ^ 
TATCGGTTT
^ ^

我怎样才能在 Python 中做到这一点？

我只有蛮力解决方案（它正在工作）：

1. 生成给定字母表上具有相同长度的所有字符串

2. 附加与给定字符串有 2 个不匹配的字符串

但是，您能建议更有效的方法吗？

Answer 1

我可能会使用 itertools。也许像

from itertools import combinations, product

def generate(s, d=2):
    N = len(s)
    letters = 'ACGT'
    pool = list(s)

    for indices in combinations(range(N), d):
        for replacements in product(letters, repeat=d):
            skip = False
            for i, a in zip(indices, replacements):
                if pool[i] == a: skip = True
            if skip: continue

            keys = dict(zip(indices, replacements))
            yield ''.join([pool[i] if i not in indices else keys[i] 
                           for i in range(N)])

然后就

list(generate("AACCGGTTT"))