在Python中实现neighborhood来查找字符串的dneighborhood

Question

输入：一个字符串模式和一个整数d。 输出：字符串邻居的集合（Pattern，d）。在

样本输入：
ACG公司 1

样本输出：
TCG公司 ACG公司 GCG公司 CCG公司 ACA公司 行动 聚合 AAG公司 自动液位计 ACC公司

解决这个问题的算法是什么？在

Answer 1

这里有一个快速而肮脏的解决方案：

chars = "ACGT"

def neighbors(pattern, d):
    assert(d <= len(pattern))

    if d == 0:
        return [pattern]

    r2 = neighbors(pattern[1:], d-1)
    r = [c + r3 for r3 in r2 for c in chars if c != pattern[0]]

    if (d < len(pattern)):
        r2 = neighbors(pattern[1:], d)
        r += [pattern[0] + r3 for r3 in r2]

    return r

以下是一些输出示例：

^{pr2}$

请注意，这给了在上完全不同于d位的邻居，而不是至多个d个位置。如果需要后者（正如示例输出所示），可以简单地将d的不同值的结果组合起来，如下所示：

def neighbors2(pattern, d):
    return sum([neighbors(pattern, d2) for d2 in range(d + 1)], [])

以下是一些输出示例：

>>> neighbors2("ACG", 1)
['ACG', 'CCG', 'GCG', 'TCG', 'AAG', 'AGG', 'ATG', 'ACA', 'ACC', 'ACT']