Ajout d'une liste et récursion (distance de Hamming) - Python 3
-
23-12-2019 - |
Question
Je suis censé écrire un programme qui prend une chaîne de code binaire et un nombre, et génère toutes les chaînes à cette distance de Hamming de la chaîne d'origine.J'ai une fonction qui fait tout, mais dans la sortie il y a des listes dans les listes.Je comprends pourquoi - la fonction est récursive et renvoie parfois une liste de valeurs possibles.
Le problème est que je ne sais pas comment le modifier pour qu'il génère des chaînes complètes.Par exemple, pour une chaîne de "0000" et une distance de Hamming "2", j'obtiens :["1['100', '010', '001']", "01['10', '01']", "001['1']"]
Mais ce que je veux c'est :
1100
1010
1001
0110
0101
0011
Le code est ci-dessous :
def hamming(num, dist):
if dist == 0:
return num
else:
outputlist = list()
for item in range(len(num)):
if len(num[item:]) > dist - 1:
if num[item] == "0":
restoflist = hamming(num[item + 1:], dist - 1)
outputlist.append(num[:item] + "1" + str(restoflist))
else:
restoflist = hamming(num[item + 1:], dist - 1)
outputlist.append(num[:item] + "0" + str(restoflist))
return outputlist
La solution
Si vous parcourez la liste renvoyée par hamming
vous devriez pouvoir assembler les chaînes de la bonne manière - comme ceci :
def hamming(num, dist):
if dist == 0:
return num
else:
outputlist = list()
for item in range(len(num)):
if len(num[item:]) > dist - 1:
if num[item] == "0":
restoflist = hamming(num[item + 1:], dist - 1)
if type(restoflist) is not str
for rest in restoflist:
outputlist.append(num[:item] + "1" + str(rest))
else
outputlist.append(num[:item] + "1" + str(restoflist))
else:
restoflist = hamming(num[item + 1:], dist - 1)
if type(restoflist) is not str
for rest in restoflist:
outputlist.append(num[:item] + "0" + str(rest))
else
outputlist.append(num[:item] + "0" + str(restoflist))
return outputlist
Autres conseils
Vous pouvez le réparer en retournant [num]
plutôt que num
dans le cas de base et dans un cas général, combinez les résultats des appels récursifs en utilisant map
et extend
plutôt que append
:
def hamming(num, dist):
if dist == 0:
return [num]
else:
outputlist = list()
for item in range(len(num)):
if len(num[item:]) > dist - 1:
if num[item] == "0":
restoflist = hamming(num[item + 1:], dist - 1)
outputlist.extend(map(lambda x: num[:item] + "1" + x, restoflist))
else:
restoflist = hamming(num[item + 1:], dist - 1)
outputlist.extend(map(lambda x: num[:item] + "0" + x, restoflist))
return outputlist
>>> hamming('0000', 2)
['1100', '1010', '1001', '0110', '0101', '0011']
>>>