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

Question

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

(例如，对于字符串'00100'和距离 4，代码返回 ['11010', '11001', '11111', '10011', '01011'] ，对于字符串 '00100' 和距离 3，代码返回 ['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) ]

每次调用时，您都会返回从输入string dist的字符串列表。 每次返回时，都必须将初始字符附加到该列表中的每个项目。

这清楚吗？

澄清

上述方法也仅生成更改字符串的方法。 "没有"更改仅指第一个字符。 例如，给定输入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在例程的递归部分。 你熟悉这种函数的结构吗？ 它由基本情况和递归情况组成。