Python 海明距离将无数循环重写为递归

Question

我创建了一个代码生成字符串，它与给定的二进制字符串的汉明距离为 n。虽然我无法用简单的递归函数重写它。 for循环逻辑中有几个序列（编辑：实际上只有一个，长度变化）但我不知道如何将它写成递归方式（函数的输入是字符串和距离（int），但在我的代码中，距离由循环嵌套的次数表示。你能帮帮我吗？

（例如，对于字符串 '00100' 和距离 4，代码 returns ['11010', '11001', '11111', '10011', '01011']，对于字符串 '00100' 和距离 3，代码 returns ['11000', '11110', '11101', '10010', '10001', '10111', '01010', '01001', '01111', '00011'])

def change(string, i):
    if string[i] == '1':
        return string[:i] + '0' + string[i+1:]
    else: return string[:i] + '1' + string[i+1:] #'0' on input


def hamming_distance(number):

    array = []
    for i in range(len(number)-3): #change first bit
        a = number
        a = change(a, i) #change bit on index i
        for j in range(i+1, len(number)-2): #change second bit
            b = a
            b = change(b, j)
            for k in range(j+1, len(number)-1): #change third bit
                c = b
                c = change(c, k)
                for l in range(k+1, len(number)): #change fourth bit
                    d = c
                    d = change(d, l)
                    array.append(d)
    return array

print(hamming_distance('00100'))

谢谢！

Answer 1

非常简单，您有三个基本情况：

len(string) == 0:    # return; you've made all the needed changes
dist == 0            # return; no more changes to make
len(string) == dist  # change all bits and return (no choice remaining)

...和两个递归案例；有无变化：

ham1 = [str(1-int(string[0])) + alter 
            for alter in change(string[1:], dist-1) ]
ham2 = [str[0] + alter for alter in change(string[1:], dist) ]

从每次调用中，您 return 一个字符串列表，这些字符串是来自输入 string 的 dist。在每个 return 上，您必须将初始字符附加到该列表中的每个项目。

清楚了吗？

澄清

上述方法也只生成那些改变字符串的方法。 "Without" 更改仅指第一个字符。例如，给定输入 string="000", dist=2，算法将执行两个操作：

'1' + change("00", 2-1)  # for each returned string, "10" and "01"
'0' + change("00", 2)    # for the only returned string, "11"

那两行 ham 行在您例程的递归部分。你熟悉这样一个函数的结构吗？它由基本案例和递归案例组成。

Python 海明距离将无数循环重写为递归

Python Hamming distance rewrite countless for cycles into recursion

python

for-loop

recursion

hamming-distance