Écrivez une fonction qui prend deux nombres naturels 𝑘 et 𝑛 comme entrées et renvoie l'ensemble de tous les n-uplets de taille 𝑘 dont la somme est 𝑛

Question

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?

python combinatorics

1

gte 25 mai 2020 à 14:27

Answer 1

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

2

owninggreendragsdude 25 mai 2020 à 11:43

Answer 2

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.

2

Pratik Joshi 25 mai 2020 à 11:45

Answer 3

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

1

Bolo 25 mai 2020 à 14:03

Écrivez une fonction qui prend deux nombres naturels 𝑘 et 𝑛 comme entrées et renvoie l'ensemble de tous les n-uplets de taille 𝑘 dont la somme est 𝑛

3 réponses

Questions connexes

De nouvelles questions

python