Calculs de sommes en évitant l'énumération exhaustive

**aCOSwt** · 04/10/2016, 09h10

Bonjour,

J'ai un N-uplet 0 < N < 27 (entier donné) de quintuplets Qi (qi1,qi2,qi3,qi4,qi5) 0 <= qij <= 5 (entiers donnés)

Je peux former des N-uplets Ni (q1x,q2y,q3z.....qNt) quels que soient 1 <= x,y,z...t <=5

Je veux connaître le nombre de N-uplets Ni tels que la somme de tous les éléments du N-uplet soit supérieure à un entier positif donné.

(v.g : Je ne suis intéressé ni par la valeur exacte de la somme ni par la connaissance précise des N-uplets matchant la condition)

Existe-t-il un moyen plus automagique que d'énumérer tous les N-uplets possibles et d'en faire la somme un par un ?

**anapurna** · 04/10/2016, 10h42

salut

en résumer tu as un tableau ou un arbre de 5 éléments de long et tu vu savoir
si il y a moyen de redistribuer cette structure en n element de long sans tout relire

Code :

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

1
2
3
4
[I1][J1,J2,J3,J4,J5]
[I2][J1,J2,J3,J4,J5]
[I3][J1,J2,J3,J4,J5]
[IN][J1,J2,J3,J4,J5]

Code :

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

1
2
3
4
[I1][J1,J2,J3,J4,J5,JN]
[I2][J1,J2,J3,J4,J5,JN]
[I3][J1,J2,J3,J4,J5,JN]
[IN][J1,J2,J3,J4,J5,JN]

la sans réfléchir je me dis que si tu redistribue les dernier element sur les premier tu n'as pas besoin de relire toutes ta structure
sachant qu'a l'origine ta structure a une certaine valeur il suffit de lui ajouter le complément

mais j'ai peut être pas tout compris

**tbc92** · 04/10/2016, 10h44

Je reformule :
tu as une grille de 27 lignes x 5 colonnes.
Dans cette grille, tu as des nombres. Tu as écris que ces nombres sont positifs et <= 5 ( 0<= qij <=5 en première ligne ) mais je me demande si ce n'est pas une erreur ; je vais donc dire que ces nombres sont positifs, et quelconques ( éventuellement des réels)

Tu veux prendre un nombre dans chaque ligne, c.a.d 27 nombres, et la combinaison retenue est "Valide" si la somme des 27 nombres est supérieure à un seuil donné S.
Et tu veux calculer combien de combinaisons valides il y a.

Première étape du traitement, si sur une ligne tu as les nombres 14 16 19 25 27, Et si le seuil S que tu vises est 300, tu peux retirer 14 à tous tes nombres ( ce qui donne 0 2 5 11 13, et le seuil devient 286).
Et pour cette ligne, tu peux mémoriser que le max est 13

Deuxième étape du traitement : Pour chaque ligne, le min est 0, et le max est connu. Si tu as des lignes avec un max égal à 100, et d'autres lignes avec un max égal à 10, ça te donne une piste d'amélioration :

Il va de toutes façons falloir faire un parcours d'arbre ; il faut mettre au début de l'arbre les lignes les plus discriminantes (celles qui ont MAX = le plus grand possible). Ainsi si tu trouves une combinaison qui a déjà atteint le seuil en sommant les 20 premières lignes, tu sais que tu peux ajouter 5^^7 à ton compteur de solutions.
Et si pour une combinaison des 20 premières lignes, la somme des max des 7 dernières lignes ne suffit pas à atteindre le seuil S, alors tu peux éliminer directement cette branche de l'arbre, sans parcourir toutes les ramifications.

**aCOSwt** · 04/10/2016, 11h41

Merci anapurna d'avoir consacré du temps sur mon problème.
Je réponds à tbc92 qui a plus détaillé.

Tu as parfaitement reformulé et compris le problème (même si je confirme que tous les éléments de la grille sont des entiers compris entre 0 et 5)

Envoyé par tbc92

Il va de toutes façons falloir faire un parcours d'arbre ; il faut mettre au début de l'arbre les lignes les plus discriminantes (celles qui ont MAX = le plus grand possible). Ainsi si tu trouves une combinaison qui a déjà atteint le seuil en sommant les 20 premières lignes, tu sais que tu peux ajouter 5^^7 à ton compteur de solutions.
Et si pour une combinaison des 20 premières lignes, la somme des max des 7 dernières lignes ne suffit pas à atteindre le seuil S, alors tu peux éliminer directement cette branche de l'arbre, sans parcourir toutes les ramifications.

Yop! Bien vu. Un bon vieux min-max de jeu d'échec de base. ! Clever 1!

et Merci.

En espérant ne fâcher personne, je ne marquerai néanmoins pas tout de suite le problème résolu car, à la vérité, je sens ce truc à la portée d'une bonne vieille opération matricielle.
En bref, je trouve qu'il pue carrément le morphisme. Mais je n'ai jamais été doué dans les espaces vectoriels alors, si quelqu'un à une idée dans ce sens, je reste à l'écoute.

Ce qui n'enlève rien à la qualité de la réponse de tbc92 que je mettrai en oeuvre par défaut.

**picodev** · 04/10/2016, 11h51

Bonjour,

Dans ton cas il y 26⁵=11.881.376 possibilités au maximum, ce qui tout compte fait est un espace de recherche relativement limité est encore accessible à une recherche exhaustive.

Maintenant si tu ne désires connaître que le nombre de solution on peut adopter une approche de programmation dynamique. Notons par C(N, seuil, k) le nombre de solutions en choisissant parmi seulement les k premiers éléments des quintuplets.
On peut remarquer que C(N,seuil, k) = taille(N)^k si seuil≤0 mais aussi que C(N,seuil,k)=somme(i=1 à taille(N); C(N,seuil-N[i][k], k-1)).
En effet si les éléments des quintuplets sont tous positifs ou nuls, le nombre de somme dont la somme est supérieure ou égale à 0 est trivialement taille(N)^k. De plus, le nombre de solutions pour un k donné peut se calculer en faisant la somme du nombre de solutions en choisissant un élément du quintuplet puis en comptant le nombre de solutions pour arriver à seuil - la valeur de l'élément choisi sur les éléments restants.
Edit: Évidemment il y a aussi le cas k=0 → si seuil=0 alors le nombre de solution est 1 sinon il vaut 0.
Et éventuellement on peut se dire que pour k=1 le nombre de solutions est simplement le nombres d'éléments en position 1 qui vérifient q[1]≥seuil …

**anapurna** · 04/10/2016, 11h55

salut

tu peut donc optimiser le fait de connaitre la valeur max des cellules
tu sais que tu n'a pas besoin de continuer si la (somme_actu + (Nb_Cel_Restante*5)) < Valeur_a_atteindre
tous ceci avant de connaitre le max de chaque ligne

**aCOSwt** · 04/10/2016, 12h36

Envoyé par picodev

...trivialement...

L'adverbe kitu!
(Quand certains cherchent les zéros non triviaux de la zeta de Riemann, moi... j'ai encore pas trouvé les triviaux alors...)

Merci pour ta contribution, je vais me retaper ta relation de récurrence à tête reposée.

**picodev** · 04/10/2016, 12h55

Bah c'est trivial dans le sens où le résultat est immédiat → tu k choix à faire à chaque choix tu as à nouveau taille(N) choix possible d'où le taille(N)^k.

Attention, tu élagues rapidement que dans le cas où il y a rapidement une solution, dans le cas «pas de solution» C=0 tu vas quand même parcourir tout l'espace de recherche qui est en O(taille(N)^taille(q)). Ton problème reste attaquable car tu as de petites valeurs pour taille(N) et taille(q).

**Prof** · 04/10/2016, 18h02

Bonjour.

Dans ton cas il y 26^5=11.881.376 possibilités au maximum, ce qui tout compte fait est un espace de recherche relativement limité

Je crains que l'espace de recherche ne soit un peu plus vaste que celà.

Vu que dans chaque ligne il faut choisir un élément parmi 5, et qu'il y a N lignes, cela fait 5^N possibilités et non pas N^5.

D'où au maximum 5^26 = 1 490 116 119 384 765 625 cas possibles.

A la vitesse d'un milliard de cas étudiés par seconde, cela fait tout de même 47 ans ...

D'où la nécessité de trouver une autre méthode qu'une recherche exhaustive.

**picodev** · 04/10/2016, 18h22

J'ai compris le problème «dans l'autre sens» il faut choisir un élément «dans chacune des 5 colonnes» avec un maximum de 26 lignes, d'où les 26⁵=11.881.376 possibilités. Mais j'ai peut-être mal compris …

Edit: En relisant, j'ai dû effectivement prendre le problème à l'envers ...

**aCOSwt** · 04/10/2016, 18h37

Envoyé par Prof

Je crains que l'espace de recherche ne soit un peu plus vaste que celà.

Vu que dans chaque ligne il faut choisir un élément parmi 5, et qu'il y a N lignes, cela fait 5^N possibilités et non pas N^5.

D'où au maximum 5^26 = 1 490 116 119 384 765 625 cas possibles.

**tbc92** · 04/10/2016, 18h48

Soyons précis,

On a 5 colonnes. sur chaque ligne on a 5 nombres, compris entre 0 et 5.
Si par hasard, tu avais : sur chaque ligne , on a les 5 nombres 1 2 3 4 et 5 ( autrement dit la même ligne répétée 27 fois) ; ça aurait bien simplifié le problème. Et dans cette hypothèse, une bonne formule à base de C(n,p) devrait donner le résultat. Aucun parcours répétitif ne serait nécessaire.

Ici, on a potentiellement 6 nombres 0 1 2 3 4 5 ... et on a potentiellement des nombres répétés 0 0 2 2 4 par exemple. Tu confirmes ?

Ma proposition exploitait le fait que MAX-MIN pouvait être très variable d'une ligne à l'autre. Elle ne marche plus vraiment dans ce que tu décris.

**picodev** · 04/10/2016, 19h55

Bon je vais reprendre le problème dans le bon sens mais de l'autre bout. Bon ce n'est qu'une idée comme ça …
Partons donc de la somme, cette somme peut être partitionnée en somme d'au plus N entiers, ces entiers étant compris entre 0 et 5. Si je ne me trompe pas il y en aura moins de 3506 possibilités. Il s'agit ensuite de déterminer le nombre de manière de constituer chacune de ses possibilités avec les N quintuplets.
Je vais essayer de creuser ça un peu plus en avant.

Edit: je me suis trompé (encore

) il y en aura bien plus que 3506 ...

**aCOSwt** · 04/10/2016, 20h55

Envoyé par tbc92

Si par hasard, tu avais : sur chaque ligne , on a les 5 nombres 1 2 3 4 et 5 ( autrement dit la même ligne répétée 27 fois) ; ça aurait bien simplifié le problème.

Simplifié à un tel point que... je m'en serais voulu de vous déranger...

Envoyé par tbc92

Ici, on a potentiellement 6 nombres 0 1 2 3 4 5 ... et on a potentiellement des nombres répétés 0 0 2 2 4 par exemple. Tu confirmes ?

Yop!
Et donc par voie de fait aussi qu'il peut y avoir plusieurs occurrences du même quintuplet.

Ton min-max suggéré dans ton premier post est probablement la meilleure solution théorique.

Le seul bémol dans la pratique est que, relativement à ce que j'ai vu pour l'instant de la distribution et des valeurs limites avec N=26 (le cas le plus fréquent) :

rangeant tous les quintuplets dans l'ordre décroissant (après "normalisation" qi - Min(qi))
rangeant ensuite le N-uplet par ordre décroissant de somme des qi

Puis lançant ton min-max, la condition (de supériorité à la valeur limite) n'est le plus souvent pas déterminable avant le 20e niveau de noeud.
Donc j'économise certes beaucoup mais bon... encore pas des masses.

**aCOSwt** · 04/10/2016, 21h18

Envoyé par picodev

Partons donc de la somme, cette somme peut être partitionnée en somme d'au plus N entiers, ces entiers étant compris entre 0 et 5. Si je ne me trompe pas il y en aura moins de 3506 possibilités. Il s'agit ensuite de déterminer le nombre de manière de constituer chacune de ses possibilités avec les N quintuplets.

Je ne sais pas si c'est ce que tu veux dire mais je crois avoir commencé à approcher le pb ainsi via une approche probabiliste.
C'est à dire de considérer que la somme de 26 entiers compris entre 0 et 5 peut prendre 5*26 = 130 valeurs distinctes.
Et que si les événements 0,1,2,3,4,5 sont équiprobables il est aisé de précalculer la probabilité de chacune des 130 valeurs de somme.

Le seul hic c'est que... les événements 0,1,2,3,4,5 ne sont pas du tout équiprobables.

EDIT : Et ceci indépendamment de cela, relativement à la distribution des 130 valeurs de somme, la valeur limite à considérer est le plus souvent au-delà de +1sigma.

**tbc92** · 04/10/2016, 21h33

Un peu de voiture, ça permet de réfléchir.
Voici la solution, qui devrait donner le résultat correct en quelques secondes.

Je déroule l'algo.. c'est plus simple pour expliquer :

Imaginons les données suivantes :
0 0 2 3 4
0 1 3 4 5
1 2 4 5 5
etc etc

Avec la 1ère ligne, il y a 2 façons dobtenir 0, 1 façon d'obtenir 2 , façon d'obtenir 3 et 1 façon d'obtenir 4
Avec la ligne 2, il y a 1 faon d'obtenir 0 1 3 4 ou 5
En combinant les lignes 1 et 2, il y a :
2 façons d'obtenir 0
2 façons d'obtenir 1
1 façon d'obtenir 2
4 façons d'obtenir 3 ( 0 +3, compté 2 fois ou 2+1 ou 3+0 )
etc etc et dernière option :
1 façon d'obtenir 9.
Le cumul des compteurs ( 2+2+1+4 + .. +1) doit donner 25, mais en fait on n'a que 9 valeurs différentes.

On combine ensuite avec la ligne 3 ... Le cumul des compteurs vaut 125, mais on a seulement 14 valeurs possibles.
etc etc

Quand on combine le cumul des 20 premières lignes avec la 21ème, on n'a donc pas 5^^20 combinaisons en stock mais seulement 100 cumuls possibles, à combiner avec 5 valeurs possibles sur la 21ème ligne.