Trouver toutes les combinaisons d'une liste de nombres avec une somme donnée

J'ai une liste de nombres, par exemple

numbers = [1, 2, 3, 7, 7, 9, 10]

Comme vous pouvez le voir, les chiffres peuvent apparaître plus d'une fois dans cette liste.

J'ai besoin d'obtenir toutes les combinaisons de ces numéros qui ont une somme donnée, par exemple 10.

Les éléments dans les combinaisons ne peuvent pas être répétées, mais chaque élément dans numbers doit être traitée de façon unique, ce qui signifie, par exemple les deux 7 dans la liste représentent les différents éléments avec la même valeur.

L'ordre est sans importance, de sorte que [1, 9] et [9, 1] sont de la même combinaison.

Il n'y a aucune restriction de longueur pour les combinaisons, [10] est aussi valide que [1, 2, 7].

Comment puis-je créer une liste de toutes les combinaisons répondant aux critères ci-dessus?

Dans cet exemple, il serait [[1,2,7], [1,2,7], [1,9], [3,7], [3,7], [10]]

OriginalL'auteur Byte Commander | 2015-12-29

  1. 15

    Vous pouvez utiliser itertools pour parcourir chaque combinaison de chaque taille possible, et de filtrer tout ce qui n'a pas de somme à 10:

    import itertools
numbers = [1, 2, 3, 7, 7, 9, 10]
result = [seq for i in range(len(numbers), 0, -1) for seq in itertools.combinations(numbers, i) if sum(seq) == 10]
print result

    Résultat:

    [(1, 2, 7), (1, 2, 7), (1, 9), (3, 7), (3, 7), (10,)]

    Malheureusement, c'est quelque chose comme O(2^N) la complexité, de sorte qu'il n'est pas approprié pour la saisie des listes de plus de, disons, 20 éléments.

    si vous êtes confus à comprendre le code ci-dessus voici une version simplifiée de ce qui précède code for i in range(1,len(a)): pour s en itertools.combinaisons(a,i): si la somme(s)==sum1: print(s)

    OriginalL'auteur Kevin

  2. 8

    La la solution de @kgoodrick offert est grande, mais je pense qu'il est plus utile en tant que générateur:

    def subset_sum(numbers, target, partial=[], partial_sum=0):
    if partial_sum == target:
        yield partial
    if partial_sum >= target:
        return
    for i, n in enumerate(numbers):
        remaining = numbers[i + 1:]
        yield from subset_sum(remaining, target, partial + [n], partial_sum + n)

    list(subset_sum([1, 2, 3, 7, 7, 9, 10], 10)) rendements [[1, 2, 7], [1, 2, 7], [1, 9], [3, 7], [3, 7], [10]].

    pourriez-vous expliquer la ligne "rendement de subset_sum(en restant, de la cible, partielle + [n], partial_sum + n)"
    Ce serait le moment de la complexité de ce code?

    OriginalL'auteur Martin Valgur

  3. 7

    Cette question a été posée, voir @msalvadores réponse ici. J'ai mis à jour le code python donné à exécuter en python 3:

    def subset_sum(numbers, target, partial=[]):
    s = sum(partial)

    # check if the partial sum is equals to target
    if s == target:
        print("sum(%s)=%s" % (partial, target))
    if s >= target:
        return  # if we reach the number why bother to continue

    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i + 1:]
        subset_sum(remaining, target, partial + [n])


if __name__ == "__main__":
    subset_sum([3, 3, 9, 8, 4, 5, 7, 10], 15)

    # Outputs:
    # sum([3, 8, 4])=15
    # sum([3, 5, 7])=15
    # sum([8, 7])=15
    # sum([5, 10])=15

    OriginalL'auteur kgoodrick