Discussion :

[antond69]

bonjour à tous

dans mon programme j'aurais besoin d'une fonction me donne toute les possibilité de longueur n avec des nombres de 0 à n (inclut) et dont la somme est égale à n.

concrètement si n = 3 je voudrait trouver une fonction qui me donne
0,0,3
0,1,2
1,1,1

j'ai trouvé la fonction combinations_with_replacement mais le souci est qu'elle me donne toutes les possibilités et pas seulement celles dont la somme vaut n
donc pour n =3 combinations_with_replacement me donne :
0,0,0
0,0,1
0,0,2
0,0,3
0,1,2
ect...

or je n'ai pas besoin des possibilité dont la somme n'est pas égale à n, et les calculer et les trier est donc une perte de temps énorme

auriez vous une idée de fonction ou une possibilité de paramétrer la fonction combinations_with_replacement qui me permettrait de résoudre mon problème


merci de votre aide

[VinsS]

Salut,

C'est toi qui dois faire le tri. Pour cela une fonction génératrice me semble appropriée.

Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
import itertools
 
def compute(n):
    vals = list(range(n+1))
    c = itertools.product(vals, repeat=n+1)
    for i in c:
        if sum(i) == n:
            yield i
 
for i in compute(3):
    print(i)
 
for i in compute(5):
    print(i)

[Sve@r]

Bonjour

c = itertools.product(vals, repeat=n+1)

Je crois qu'il faut mettre "repeat=n". Avec "n+1" on a un chiffre de trop (4 chiffres quand on cherche 3, 6 chiffres quand on cherche 5)...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    for i in c:
        if sum(i) == n:
            yield i

yield from (i for i in c if sum(i) == n)

[VinsS]

Ben, le PO a écrit n inclus

[Sve@r]

Ben, le PO a écrit n inclus

Oui, je ne parle pas de la valeur maximale des nombres de la liste, mais du nombre de ces nombres (il a demandé "de longueur n")
Avec (par exemple) compute(3) le list(range(n+1)) initialise bien vals=[0, 1, 2, 3] ça c'est ok... mais en écrivant repeat=n+1 tu génères (3, 0, 0, 0) alors que le PO a demandé (3, 0, 0) qui s'obtient avec repeat=n.

[antond69]

super ça fonctionne et surtout c'est plus rapide

il y a des opérations qui sont ensuite effectuer à chaque fois sur les valeurs trouvées donc il fallait optimiser ça

pour vous donner une idée avec n=8

avant : temps de calcul de 0.0568537712097168 secondes
maintenant et grâce à vous : temps de calcul de 0.005019664764404297 secondes

soit 10x plus rapide alors encore un grand merci à vous tous

[wiztricks]

Salut,

Pour cela une fonction génératrice me semble appropriée.

combinations_with_replacement est déjà un générateur.

auriez vous une idée de fonction ou une possibilité de paramétrer la fonction combinations_with_replacement qui me permettrait de résoudre mon problème

Soit vous écrivez une fonction qui filtre ce qui est retourné par combinations_with_replacement (*), soit vous avez un algo. qui permette de fabriquer çà sans passer par la génération de toutes les combinaisons puis le filtrage.

(*) la documentation vous donne un exemple de code de combinations_with_replacement que vous mouvez "améliorer". Ceci dit filtrer avant de les remonter ou après ne changera pas grand chose.

- W