Python Hamming distance rewrite countless for cycles into recursion

Question

I have created a code generating strings which have hamming distance n from given binary string. Though I'm not able to rewrite this in a simple recursive function. There are several sequences (edit: actually only one, the length change) in the for loops logic but I don't know how to write it into the recursive way (the input for the function is string and distance (int), but in my code the distance is represented by the count of nested for cycles. Could you please help me?

(e.g. for string '00100' and distance 4, code returns ['11010', '11001', '11111', '10011', '01011'], for string '00100' and distance 3, code 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'))

Thank you!

Answer 1

Very briefly, you have three base cases:

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)

... and two recursion cases; with and without the change:

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) ]

From each call, you return a list of strings that are dist from the input string. On each return, you have to append the initial character to each item in that list.

Is that clear?

CLARIFICATION

The above approach also generates only those that change the string. "Without" the change refers to only the first character. For instance, given input string="000", dist=2, the algorithm will carry out two operations:

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

Those two ham lines go in the recursion part of your routine. Are you familiar with the structure of such a function? It consists of base cases and recursion cases.