Python: Comment trouver dans une liste de nombres ceux dont la somme est égale à nombre défini

Comme indiqué dans le titre, j'ai une liste de nombre, par exemple 5, 10, 25, 30, 45, 60 et j'aimerais savoir quels sont ceux, quand on les additionne, qui me donne le résultat 35 par exemple.

Avec ces nombres, facile, il y a 10 + 25 mais également 5 + 30, mais quand on a une liste de nombres comme celle-ci 8.42, 6.94, 5.40, 1.77, 4.32, 4.26, 3.49, 2.33, 3.90, 1.09 (avec des décimales, c'est plus fun) et que je veux que la somme soit égale à 29.44, c'est un peu plus compliqué.

J'ai imaginé cette fonction en Python qui me permet de trouver le résultat.
Bien évidemment, plus il y a de nombres dans la liste de départ, plus le temps de calcul est long.
Pour m'aider, j'utilise les classes permutations et accumulate du module itertools ainsi que la classe Decimal du module decimal.

Peut-être auriez vous des idées d'amélioration ?

Voici la fonction.
Toutes les lignes sont commentées pour une meilleure compréhension.

from itertools import permutations
from itertools import accumulate
from decimal import Decimal


def trouve_les_arguments_de_la_somme():
    t = Decimal('29.44') # la somme à trouver
    l = [8.42, 6.94, 5.40, 1.77, 4.32, 4.26, 3.49, 2.33, 3.90, 1.09] # la liste des arguments, 10 au total
    l = [Decimal(str(x)) for x in l] # je convertis les arguments en objet "Decimal"
    l = [x for x in l if x <= t] # je conserve uniquement les valeurs inférieures ou égales à la somme à trouver
    z = permutations(l, len(l)) # j'utilise la classe permutations afin de générer toutes les combinaisons possible, 3 628 800 dans mon cas [factorial(10)]
    se = set() # je créé un set afin d'y stocker toutes les solutions possible
        for x in z: # je parcours toutes les combinaisons possible
            s = list(accumulate(x)) # pour chaque combinaison, je calcul la somme cumulée à l'aide de la classe accumulate
            if t in s: # si ma somme à trouver est dans la liste des sommes cumulées
                i = s.index(t) # je recherche la position de ma somme dans la liste
                se.add(tuple(sorted(x[:i + 1]))) # je récupère dans ma combinaison tous les arguments concernés grâce à mon index i et je les trie par ordre croissant avant de les ajouter à mon set
    for i in se:
            print(str(i)) # j'affiche les résultats

(Decimal('1.09'), Decimal('1.77'), Decimal('2.33'), Decimal('3.49'), Decimal('5.4'), Decimal('6.94'), Decimal('8.42'))

Dans mon cas, je n'ai qu'une seule solution possible (trouvée en 10 sec max).

Ajouter un commentaire

Filtered HTML

  • Les adresses de pages web et de messagerie électronique sont transformées en liens automatiquement.
  • Tags HTML autorisés : <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Les lignes et les paragraphes vont à la ligne automatiquement.

Plain text

  • Aucune balise HTML autorisée.
  • Les adresses de pages web et de messagerie électronique sont transformées en liens automatiquement.
  • Les lignes et les paragraphes vont à la ligne automatiquement.
CAPTCHA
Cette question permet de s'assurer que vous êtes un utilisateur humain et non un logiciel automatisé de pollupostage.
CAPTCHA visuel
Entrez les caractères (sans espace) affichés dans l'image.