En python 3, j'essaie d'écrire une fonction qui prend deux nombres naturels 𝑘 et 𝑛 comme entrées et renvoie l'ensemble de tous les tuples de taille 𝑘 qui totalisent 𝑛.
J'ai construit les fonctions suivantes:
def get_tuples(length, total):
if length == 1:
yield (total,)
return
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
yield (i,) + t
Qui avec, par exemple, list (get_tuples (2, 8)) renvoie les résultats corrects, et:
def get_tuples(length, total):
if length == 1:
return [(total,)]
comp = []
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
comp.append((i,) + t)
return comp
Qui renvoie cependant un résultat erroné (c'est-à-dire un seul tuple). Quelqu'un peut-il expliquer pourquoi et comment corriger la deuxième fonction?
3 réponses
Placez simplement le retour un retrait:
def get_tuples(length, total):
if length == 1:
return [(total,)]
comp = []
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
comp.append((i,) + t)
return comp
Edit: Assurez-vous de comprendre pourquoi
Voici:
def get_tuples(length, total):
if length == 1:
return [(total,)]
comp = []
for i in range(total + 1):
for t in get_tuples(length - 1, total - i):
comp.append((i,) + t)
return comp
Retirez l'instruction return de la boucle.
La réponse de owninggreendragsdude est la bonne, car elle montre exactement la seule chose que vous devez changer dans votre code pour que cela fonctionne.
Cependant, si vous vous demandez comment vous débarrasser de la récursivité et accélérer le code en même temps, voici une solution:
def get_tuples_optimized(length, total):
comp = []
# Stack of partial tuples to process, initialized with an empty tuple
todo = [(total, tuple())]
# Loop as long as we have partial tuples on our stack
while todo:
# Take the next partial tuple
amount_left, partial_tuple = todo.pop()
if len(partial_tuple) == length - 1:
# Put all that is left as the last element
comp.append(partial_tuple + (amount_left,))
else:
# Add all possible extensions-by-one to our stack
for i in range(amount_left + 1):
extended_tuple = partial_tuple + (i,)
todo.append((amount_left - i, extended_tuple))
return comp
Questions connexes
De nouvelles questions
python
Python est un langage de programmation multi-paradigme, typé dynamiquement et polyvalent. Il est conçu pour être rapide à apprendre, comprendre, utiliser et appliquer une syntaxe propre et uniforme. Veuillez noter que Python 2 est officiellement hors support à partir du 01-01-2020. Néanmoins, pour les questions Python spécifiques à la version, ajoutez la balise [python-2.7] ou [python-3.x]. Lorsque vous utilisez une variante Python (par exemple, Jython, PyPy) ou une bibliothèque (par exemple, Pandas et NumPy), veuillez l'inclure dans les balises.