1
votes

Trouver (ou générer) toutes les combinaisons possibles (à une longueur donnée) de nombres positifs qui égalent une somme donnée (python)

J'essaie de trouver le moyen le plus efficace de trouver toutes les combinaisons de nombres qui égalent une somme donnée.

Par exemple: Vous cherchez à trouver tous les combos à 3 chiffres dont la somme = 3

Sortie souhaitée: [0,0,3], [0,3,0], [3,0,0], [1,1,1], [1,2,0], [1,2,0], [2 , 1,0], [2,0,1]

En termes d'application, j'essaie de générer des listes de toutes les combinaisons à 3 chiffres qui valent 100. J'ai essayé d'y parvenir en créant une liste contenant les nombres 0 - 100 à utiliser comme argument d'entrée et le code suivant ci-dessous:

 def weightList():
     l=[]
     for x in range(0,101):
         l.append(x)
     return l

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

     # check if the partial sum is equals to target
        if (s == target)&(len(partial) == LoanCount): 
            print(partial)
        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]) 
  o=weightList()
  subset_sum(o,100)

Le problème est que cela prend trop de temps en raison du nombre d'itérations qu'il doit effectuer . Je dois également inclure des combinaisons d'éléments répétitifs et un ordre / séquence d'éléments différent. Cette méthode ne fonctionne pas. Quelqu'un peut-il me fournir une méthode beaucoup plus rapide / efficace pour obtenir le résultat souhaité?

python list loops

0 commentaires

3 Réponses :

0
votes

Jetez un œil au problème des étoiles et barres . Le fait est que même la solution la plus rapide possible sera toujours très lente en raison du grand nombre de réponses (qui peuvent être de l’ordre de N!), Et que toute solution correcte doit toutes les obtenir.

Voici ma photo à une solution:

def get_combinations(n, k): # gets all lists of size k summing to n
    ans = []
    def solve(rem, depth, k, cur):
        if depth == k:
            ans.append(cur)
        elif depth == k-1:
            solve(0, depth+1, k, cur + [rem])
        else:
            for i in range(rem+1):
                solve(rem-i, depth+1, k, cur+[i])
    solve(n, 0, k, [])
    return ans

print (get_combinations(3,3))

C'est à peu près aussi rapide que possible pour trouver toutes les listes possibles. Cependant, si vous souhaitez simplement trouver le nombre de ces listes, vous pouvez le faire beaucoup plus rapidement en utilisant la méthode des étoiles et des barres référencée ci-dessus.

2 commentaires

Merci beaucoup, cela a été très utile

Aucun problème! Heureux d'aider.

1
votes

vous pouvez utiliser un générateur pour trouver toutes les combinaisons possibles de 3 nombres qui égalent une somme donnée:

[(0, 0, 3),
 (0, 1, 2),
 (0, 2, 1),
 (0, 3, 0),
 (1, 0, 2),
 (1, 1, 1),
 (1, 2, 0),
 (2, 0, 1),
 (2, 1, 0),
 (3, 0, 0)]

sortie:

def gen_combo_target(s):
    for i in range(s + 1):
        s2 = s - i
        for j in range(s2 + 1):
            yield (i, j , s - i - j)

list(gen_combo_target(3))

p >

0 commentaires

0
votes

Vous pouvez également utiliser un générateur et des outils python comme ceci:

9.53 Âµs Â± 177 ns per loop (mean Â± std. dev. of 7 runs, 100000 loops each)

result:

[(0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0), (3, 0, 0)]

et il peut fonctionner environ 10 us en ma machine:

from itertools import product

def comb(nx):
    list_gen = (n for n in range(nx+1))
    list_ = (list(list_gen))
    prod = [seq for seq in product(list_, list_, list_) if sum(seq) == nx]    
    print(list(prod))

0 commentaires