Discussion :

[senacle]

Bonjour,

Soit une somme S = 270.
Soit 9 nombres qui varient de 0 à S.
Quelle est la liste des 9 nombres dont la somme est <= S ?

Par exemple
270 0 0 0 0 0 0 0 0
269 0 0 0 0 0 0 0 0
269 1 0 0 0 0 0 0 0
269 0 1 0 0 0 0 0 0
...
268 0 0 0 0 0 0 0 0
....
268 1 1 0 0 0 0 0 0
268 1 0 1 0 0 0 0 0
....
268 0 1 1 0 0 0 0 0
268 0 1 0 1 0 0 0 0
.....
15 0 0 0 0 0 0 0
36 0 25 0 18 0 0 0 0
.....
0 0 0 0 269 0 0 0 0
0 0 0 0 269 1 0 0 0
....

La position du nombre dans la ligne est à prendre en compte.
269 1 0 0 0 0 0 0 0
0 0 0 0 269 1 0 0 0
sont deux combinaisons qui doivent être conservées.

Pour l'instant, j'ai fait une boucle récursive qui génèrent toutes les combinaisons des 9 nombres.
Je teste à chaque fois leur somme.
Si <= S, je garde.

Mais ça fait 270⁹ combinaisons à tester......

Y aurait-il plus rapide pour trouver les combinaisons qui satisfont à la somme sans tester toutes les combinaisons ?

[Flodelarab]

Bonjour

Chaque nombre est ou n'est pas dans la combinaison finale. Donc 2 cas possibles pour chaque 9 nombres, soit 2⁹=512 valeurs possibles.

Vu l'énoncé, je les écrirais tous (les 512) et je supprimerais ceux qui dépassent S, en prenant ceux qui ont 9 nombres puis ceux qui ont 8 nombres (sous-ensemble du précédent), puis ceux qui ont 7 nombres (sous-ensemble du précédent), puis 6, puis 5, puis 4, etc

[senacle]

Chacun des 9 nombres peut valoir entre 0 et 270.
Et on peut avoir plusieurs fois le même nombre sur chaque ligne.

J'ai compété mon premier post :
La position du nombre dans la ligne est à prendre en compte.
269 1 0 0 0 0 0 0 0
0 0 0 0 269 1 0 0 0
sont deux combinaisons qui doivent être conservées.

[pseudocode]

Bonjour,

Y aurait-il plus rapide pour trouver les combinaisons qui satisfont à la somme sans tester toutes les combinaisons ?

Comme on le voit dans ton exemple, on s'aperçoit assez vitre qu'on peut décomposer la liste.

Si on appelle SubsetSum(N,S) les listes de N nombres dont la somme est égale à S, alors

SubsetSum(9,270) = {SubsetSum(1,270) X SubsetSum(8, 0)}, {SubsetSum(1,269) X SubsetSum(8, 1)}, {SubsetSum(1,268) X SubsetSum(8, 2)}, ...

Ou, d'une manière générale

SubsetSum(N,S) = SubsetSum(N-i,S-k) X SubsetSum(i,k) pour k parcourant [0,S], et i une valeur arbitraire dans [0,N]

avec
SubsetSum(0,a) = vide
SubsetSum(1,a) = {a}


Ca nous fait donc un tableau de S*N listes à remplir par récursion, puis un algo assez simple pour "piocher" les bonnes cases du tableau.

[senacle]

Si on appelle SubsetSum(N,S) les listes de N nombres dont la somme est égale à S

J'avais bien regardé du côté de l'algorithme SubsetSum, mais il ne fait que pour =.
Je cherche <=

SubsetSum(N,S) = SubsetSum(N-i,S-k) X SubsetSum(i,k)

Comment traduire X ? C'est un produit de matrices ?

un tableau de S*N listes à remplir

J'ai déjà fait un essai avec ma méthode avec les 9 nombres valant 0 ou 30, j'obtiens 48 556 combinaisons à retenir.

0 0 0 0 0 0 0 0 30
0 0 0 0 0 0 0 30 0
0 0 0 0 0 0 0 30 30
0 0 0 0 0 0 30 0 0
0 0 0 0 0 0 30 0 30
0 0 0 0 0 0 30 30 0
0 0 0 0 0 0 30 30 30
......
30 30 30 30 30 30 30 30 30


Ca ne représente qu'une partie de ce dont j'ai besoin ( rappel : les 9 nombres valent entre 0 et 270).
On est donc loin des S*N = 270*9 = 2430.

[pseudocode]

J'avais bien regardé du côté de l'algorithme SubsetSum, mais il ne fait que pour =.
Je cherche <=

Si tu as une solution pour la somme exacte, les solutions de ton problème ont forcément des coordonnées inférieures:

Solution Somme=270 --> (200,60,10,0,0,0,0,0,0)

Solution Somme<=270 --> ([0-200],[0-60],[0-10],0,0,0,0,0,0)

Comment traduire X ? C'est un produit de matrices ?

Un produit cartésien: {a,b} x {1,2} = (a,1), (a,2), (b,1), (b,2)

Ca ne représente qu'une partie de ce dont j'ai besoin ( rappel : les 9 nombres valent entre 0 et 270).
On est donc loin des S*N = 270*9 = 2430.

Aucune méthode ne va diminuer le nombre de solutions à ton problème.
Là je proposais juste de construire les solutions finales en concaténant les solutions intermédiaires pour que ce soit plus rapide.
Mais le nombre de solution de solutions à ton problème reste de toutes façons très grand (cf. "Partition d'un entier" sur wikipedia).

[senacle]

Si tu as une solution pour la somme exacte, les solutions de ton problème ont forcément des coordonnées inférieures:

Solution Somme=270 --> (200,60,10,0,0,0,0,0,0)

Solution Somme<=270 --> ([0-200],[0-60],[0-10],0,0,0,0,0,0)

OK, compris.


Je vais essayer de créer le code en php.

(cf. "Partition d'un entier" sur wikipedia).

En fait, ce serait plutôt la composition d'un entier dans mon cas : l'ordre est important.
https://fr.wikipedia.org/wiki/Compos...ombinatoire%29

[tbc92]

@flodelarab : tu t'es planté. Ton raisonnement donne le même résultat pour S=270, ou S=280 , ça ne va pas.

@senacle : tu veux compter le nombre de solutions, ou tu veux les recenser toutes ?
Si tu veux les recenser toutes, je partirais sur une récursivité.
Mais il va y en avoir BEAUCOUP !

[Flodelarab]

@flodelarab : tu t'es planté. Ton raisonnement donne le même résultat pour S=270, ou S=280 , ça ne va pas.

Je me suis trompé car tous les nombres peuvent prendre n'importe quelle valeur.
Mais dire que cela donne le même résultat pour 270 et 280 est faux.

[Prof]

Bonjour.

tbc92 a écrit :

Mais il va y en avoir BEAUCOUP !

Effectivement : il y a exactement 24 777 581 655 399 430 listes [a1,a2,a3,a4,a5,a6,a7,a8,a9] telles que a1+a2+a3+a4+a5+a6+a7+a8+a9 <= 270.

Si on veut les afficher à l'écran, en supposant qu'on peut en afficher 1 000 000 par seconde, cela prendra 785 ans.

Si on veut les stocker dans un fichier, en tenant compte qu'il faut 18 octets par liste, le fichier fera 445 996 469 797 189 740 octets, soit 445 996 469 Go.

Et, en supposant qu'on dispose d'un moyen de stockage et qu'on peut écrire 1 000 000 000 octets par seconde, l'écriture du fichier prendra 14 ans.

En résumé, quel que soit le langage utilisé pour l'écrire, le programme sera difficile à exécuter ...

[senacle]

il y a exactement 24 777 581 655 399 430 listes [a1,a2,a3,a4,a5,a6,a7,a8,a9] telles que a1+a2+a3+a4+a5+a6+a7+a8+a9 <= 270.

En résumé, quel que soit le langage utilisé pour l'écrire, le programme sera difficile à exécuter ...

Oulà !!!!
Effectivement, ça ne va pas être possible.
Quelle formule as-tu utilisée pour faire ce calcul ?

J'ai trouvé celle-ci
The formula for the number of compositions of N into K parts is

Code :

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

Number = ( N + K - 1 )! / ( N! * ( K - 1 )! )

Ce qui donnerait pour mon cas :
(270 + 9 - 1)! / (270! * (9-1)!) = 278! / (270! * 8!) = (278*277*276*275*274*273*272*271) / (8*7*6*5*4*3*2*1) = 79 927 682 760 000

Ca ne fait plus que 5,4 mois pour l'écriture du fichier

[senacle]

@senacle : tu veux compter le nombre de solutions, ou tu veux les recenser toutes ?
Si tu veux les recenser toutes, je partirais sur une récursivité.
Mais il va y en avoir BEAUCOUP !

les recenser toutes

[senacle]

Après recherche sur le net, j'ai trouvé des descriptions d'algorithme et plusieurs solutions permettant le calcul de partitions ou de compositions.

Pour ceux qui seraient intéressés :
http://theory.cs.uvic.ca/inf/nump/NumPartition.html
http://jeromekelleher.net/category/combinatorics.html
https://arxiv.org/pdf/0909.2331.pdf
https://www.semanticscholar.org/pape...e1a5be1bb2/pdf
https://www.researchgate.net/profile...76c0000000.pdf
http://www.mathworks.com/matlabcentr...ontent/colex.m
http://arxiv.org/pdf/0909.2331v2.pdf
https://blogs.msdn.microsoft.com/old...14-00/?p=1263/
https://blogs.msdn.microsoft.com/old...0714-00/?p=513
https://gist.github.com/jasonmc/989158
http://stackoverflow.com/questions/1...ger-partitions
http://www.se16.info/js/partitions.htm
http://homeomath2.imingo.net/algorithme1.htm
http://www.computing-wisdom.com/comp...ngs/fasc3b.pdf

[senacle]

J'ai essayé d'adapter plusieurs des algorithmes en php.

Le plus adapté à mon besoin, et le plus rapide, est celui-ci, en php :

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
16
17
18
19
20
21
22
23
24
25
26
27
28
function compositions($t=2,$s=2){
    //~"""knuth 7.2.1.3"""
    $q = array_fill(0, $t, 0);
    $r = "";
    $q[0] = $s;
    while (true){
        yield $q;
        if ($q[0] == 0){
            if ($r==$t-1){
                break;
            }else{
                $q[0] = $q[$r] - 1;
                $q[$r] = 0;
                $r = $r + 1;
			}
        }else{
            $q[0] = $q[0] - 1;
            $r = 1;
		}
        $q[$r] = $q[$r] + 1;
	}
}
 
 
foreach(compositions($nombre_de_parties, $nombre_a_decomposer) as $compositions) {
	$resultat_compo .= "<br/>".implode(" + ", $compositions);
	$nb_compositions += 1;
}

Vous remarquerez le yield qui assure la récursivité (je n'ai pas tout compris au fonctionnement du yield, mais bon, ça donne les compositions)



Pour nombre_a_decomposer = 2 en nombre_de_parties = 9, on obtient 45 compositions (ça vérifie bien la formule du nombre de combinaisons que j'indique dans le post post n° 11).

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0
1 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0
0 + 2 + 0 + 0 + 0 + 0 + 0 + 0 + 0
1 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0
0 + 1 + 1 + 0 + 0 + 0 + 0 + 0 + 0
0 + 0 + 2 + 0 + 0 + 0 + 0 + 0 + 0
1 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 0
0 + 1 + 0 + 1 + 0 + 0 + 0 + 0 + 0
0 + 0 + 1 + 1 + 0 + 0 + 0 + 0 + 0
0 + 0 + 0 + 2 + 0 + 0 + 0 + 0 + 0
1 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0
0 + 1 + 0 + 0 + 1 + 0 + 0 + 0 + 0
0 + 0 + 1 + 0 + 1 + 0 + 0 + 0 + 0
0 + 0 + 0 + 1 + 1 + 0 + 0 + 0 + 0
0 + 0 + 0 + 0 + 2 + 0 + 0 + 0 + 0
1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 0
0 + 1 + 0 + 0 + 0 + 1 + 0 + 0 + 0
0 + 0 + 1 + 0 + 0 + 1 + 0 + 0 + 0
0 + 0 + 0 + 1 + 0 + 1 + 0 + 0 + 0
0 + 0 + 0 + 0 + 1 + 1 + 0 + 0 + 0
0 + 0 + 0 + 0 + 0 + 2 + 0 + 0 + 0
1 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 0
0 + 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0
0 + 0 + 1 + 0 + 0 + 0 + 1 + 0 + 0
0 + 0 + 0 + 1 + 0 + 0 + 1 + 0 + 0
0 + 0 + 0 + 0 + 1 + 0 + 1 + 0 + 0
0 + 0 + 0 + 0 + 0 + 1 + 1 + 0 + 0
0 + 0 + 0 + 0 + 0 + 0 + 2 + 0 + 0
1 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0
0 + 1 + 0 + 0 + 0 + 0 + 0 + 1 + 0
0 + 0 + 1 + 0 + 0 + 0 + 0 + 1 + 0
0 + 0 + 0 + 1 + 0 + 0 + 0 + 1 + 0
0 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 0
0 + 0 + 0 + 0 + 0 + 1 + 0 + 1 + 0
0 + 0 + 0 + 0 + 0 + 0 + 1 + 1 + 0
0 + 0 + 0 + 0 + 0 + 0 + 0 + 2 + 0
1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1
0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 + 1
0 + 0 + 1 + 0 + 0 + 0 + 0 + 0 + 1
0 + 0 + 0 + 1 + 0 + 0 + 0 + 0 + 1
0 + 0 + 0 + 0 + 1 + 0 + 0 + 0 + 1
0 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 1
0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 + 1
0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 + 1
0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 + 2

Pour nombre_a_decomposer = 10 en nombre_de_parties = 9, on obtient 43 758 compositions.

[tbc92]

A priori, la formule que tu as trouvée sur le Net donne la réponse à la question :
Combien y a-t-il de combinaisons dont la somme = S ?

Mais ta question était :
Combien y a-t-il de combinaisons dont la somme <= S ?

Une chose est sûre, écrire un fichier avec toutes les solutions, ce n'est pas réaliste. Il va falloir que tu trouves un plan B, dans lequel tu n'aurais pas besoin de ce recensement.

[Prof]

Bonjour.

Je vais donner quelques explications sur la formule que j'ai utilisée.

Notons f(N,p) le nombre de p-uplets (a1,a2,...,ap) d'entiers positifs ou nuls tels que a1 +a2 + ... +ap = N.

Il est évident que f(N,1) = 1.
Afin de calculer f(N,p), considérons le dernier terme du p-uplet.
Si ap vaut 0, alors la somme des p-1 premiers termes vaut N et donc le cas ap = 0 se produit f(N,p-1) fois.
Si ap vaut 1, alors la somme des p-1 premiers termes vaut N-1 et donc le cas ap = 1 se produit f(N-1,p-1) fois.
etc ...
Si ap vaut N, alors la somme des p-1 premiers termes vaut 0 et donc le cas ap = N se produit f(0,p-1) fois.
On a donc la formule f(N,p) = f(0,p-1) + f(1,p-1) + ... + f(N,p-1).

f(N,p) peut donc se calculer par récurrence sur p, sachant que f(N,1) vaut 1.

Posons

Alors

D'autre part, la formule de Pascal

donne

etc ...
Finalement, on a


( on a pour k < p-1 )

D'où


Soit : g(N,p) = g(0,p-1) + g(1,p-1) + ... + g(N,p-1)

Ainsi, f et g vérifient la même relation de récurrence.
Comme f(N,1) = g(N,1), on a f = g.

D'où la formule


Revenons au problème initial.

Si on note S(N,p) le nombre de p-uplets (a1,a2,...,ap) tels que a1 + a2 + ... +ap <= N, alors S(N,p) = f(0,p) + f(1,p) + ... + f(N,p).

En comparant avec la formule de récurrence de f, on voit que S(N,p) = f(N,p+1).

On a donc la formule


Pour N = 270 et p = 9, on a

ce qui explique le nombre donné dans mon post précédent.

Pour N = 2 et p = 9, on a

et non 45.

Vérification.

J'ai écrit une procédure en Python qui affiche toutes les solutions :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 def S(N):                         # pour p = 9
    effectif = 0
    for a1 in range(N+1):
      for a2 in range(N+1):
        for a3 in range(N+1):
          for a4 in range(N+1):
            for a5 in range(N+1):
              for a6 in range(N+1):
                for a7 in range(N+1):
                  for a8 in range(N+1):
                    for a9 in range(N+1):
                      if (a1+a2+a3+a4+a5+a6+a7+a8+a9) <= N :
                          effectif = effectif +1
                          print(effectif,[a1,a2,a3,a4,a5,a6,a7,a8,a9])

Quand je l'utilise, Python me donne bien 55 solutions :

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
>>> S(2)
1 [0, 0, 0, 0, 0, 0, 0, 0, 0]
2 [0, 0, 0, 0, 0, 0, 0, 0, 1]
3 [0, 0, 0, 0, 0, 0, 0, 0, 2]
4 [0, 0, 0, 0, 0, 0, 0, 1, 0]
5 [0, 0, 0, 0, 0, 0, 0, 1, 1]
6 [0, 0, 0, 0, 0, 0, 0, 2, 0]
7 [0, 0, 0, 0, 0, 0, 1, 0, 0]
8 [0, 0, 0, 0, 0, 0, 1, 0, 1]
9 [0, 0, 0, 0, 0, 0, 1, 1, 0]
10 [0, 0, 0, 0, 0, 0, 2, 0, 0]
11 [0, 0, 0, 0, 0, 1, 0, 0, 0]
12 [0, 0, 0, 0, 0, 1, 0, 0, 1]
13 [0, 0, 0, 0, 0, 1, 0, 1, 0]
14 [0, 0, 0, 0, 0, 1, 1, 0, 0]
15 [0, 0, 0, 0, 0, 2, 0, 0, 0]
16 [0, 0, 0, 0, 1, 0, 0, 0, 0]
17 [0, 0, 0, 0, 1, 0, 0, 0, 1]
18 [0, 0, 0, 0, 1, 0, 0, 1, 0]
19 [0, 0, 0, 0, 1, 0, 1, 0, 0]
20 [0, 0, 0, 0, 1, 1, 0, 0, 0]
21 [0, 0, 0, 0, 2, 0, 0, 0, 0]
22 [0, 0, 0, 1, 0, 0, 0, 0, 0]
23 [0, 0, 0, 1, 0, 0, 0, 0, 1]
24 [0, 0, 0, 1, 0, 0, 0, 1, 0]
25 [0, 0, 0, 1, 0, 0, 1, 0, 0]
26 [0, 0, 0, 1, 0, 1, 0, 0, 0]
27 [0, 0, 0, 1, 1, 0, 0, 0, 0]
28 [0, 0, 0, 2, 0, 0, 0, 0, 0]
29 [0, 0, 1, 0, 0, 0, 0, 0, 0]
30 [0, 0, 1, 0, 0, 0, 0, 0, 1]
31 [0, 0, 1, 0, 0, 0, 0, 1, 0]
32 [0, 0, 1, 0, 0, 0, 1, 0, 0]
33 [0, 0, 1, 0, 0, 1, 0, 0, 0]
34 [0, 0, 1, 0, 1, 0, 0, 0, 0]
35 [0, 0, 1, 1, 0, 0, 0, 0, 0]
36 [0, 0, 2, 0, 0, 0, 0, 0, 0]
37 [0, 1, 0, 0, 0, 0, 0, 0, 0]
38 [0, 1, 0, 0, 0, 0, 0, 0, 1]
39 [0, 1, 0, 0, 0, 0, 0, 1, 0]
40 [0, 1, 0, 0, 0, 0, 1, 0, 0]
41 [0, 1, 0, 0, 0, 1, 0, 0, 0]
42 [0, 1, 0, 0, 1, 0, 0, 0, 0]
43 [0, 1, 0, 1, 0, 0, 0, 0, 0]
44 [0, 1, 1, 0, 0, 0, 0, 0, 0]
45 [0, 2, 0, 0, 0, 0, 0, 0, 0]
46 [1, 0, 0, 0, 0, 0, 0, 0, 0]
47 [1, 0, 0, 0, 0, 0, 0, 0, 1]
48 [1, 0, 0, 0, 0, 0, 0, 1, 0]
49 [1, 0, 0, 0, 0, 0, 1, 0, 0]
50 [1, 0, 0, 0, 0, 1, 0, 0, 0]
51 [1, 0, 0, 0, 1, 0, 0, 0, 0]
52 [1, 0, 0, 1, 0, 0, 0, 0, 0]
53 [1, 0, 1, 0, 0, 0, 0, 0, 0]
54 [1, 1, 0, 0, 0, 0, 0, 0, 0]
55 [2, 0, 0, 0, 0, 0, 0, 0, 0]

[senacle]

Je vais donner quelques explications sur la formule que j'ai utilisée.

Mes cours de maths sont lointains, lointains....mais j'ai compris.

Pour N = 2 et p = 9, on a

et non 45.

J'aurais effectivement dû vérifier mes calculs et constaté qu'il manque 10 combinaisons (celles avec un seul 1 et celles avec que des 0).
Je vais revoir mon algorithme, qui donne les compositions (donc pour la somme =) et pas les "sous-compositions" (pour la somme <).

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 def S(N):                         # pour p = 9
    effectif = 0
    for a1 in range(N+1):
      for a2 in range(N+1):
        for a3 in range(N+1):
          for a4 in range(N+1):
            for a5 in range(N+1):
              for a6 in range(N+1):
                for a7 in range(N+1):
                  for a8 in range(N+1):
                    for a9 in range(N+1):
                      if (a1+a2+a3+a4+a5+a6+a7+a8+a9) <= N :
                          effectif = effectif +1
                          print(effectif,[a1,a2,a3,a4,a5,a6,a7,a8,a9])

J'imagine qu'avec ces 9 boucles imbriquées, le temps de calcul explose, comme dit au début.
Les différents algorithmes et théories que j'ai trouvés essaient d'optimiser ce temps.

[senacle]

A priori, la formule que tu as trouvée sur le Net donne la réponse à la question :
Combien y a-t-il de combinaisons dont la somme = S ?

Effectivement

Mais ta question était :
Combien y a-t-il de combinaisons dont la somme <= S ?

Exact.

[tbc92]

Ici, il y aurait une optimisation toute simple :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
def S(N):                         # pour p = 9
    effectif = 0
    for a1 in range(N+1):
      for a2 in range(N+1-a1):
        for a3 in range(N+1-a1-a2):
          for a4 in range(N+1-a1-a2-a3):
            for a5 in range(N+1-a1-a2-a3-a4):
              for a6 in range(N+1-a1-a2-a3-a4-a5):
                for a7 in range(N+1-a1-a2-a3-a4-a5-a6):
                  for a8 in range(N+1-a1-a2-a3-a4-a5-a6-a7):
                    for a9 in range(N+1-a1-a2-a3-a4-a5-a6-a7-a8):
                        effectif = effectif +1
                        print(effectif,[a1,a2,a3,a4,a5,a6,a7,a8,a9])

Là, on a un algorithme optimum, à peu de chose près. Mais ça n'empêche que pour S=270, on va devoir écrire BEAUCOUP de lignes, et ce temps là est incompressible.
Et Prof a fait une estimation de ce temps, qui serait de plusieurs années.

[wiwaxia]

Bonjour,

Des énumérations de listes d'entiers m'ont posé des problèmes analogues, mais là on arrive à des valeurs démentes.

Il est effectivement hors de question d'inventorier toutes les solutions possibles, et tbc92 a eu la bonne idée de restreindre l'énumération; mais il faut cependant aller beaucoup plus loin.
Voilà ce que je propose:
1°) Enoncer pour une somme maximale donnée (s) toutes les listes de 9 entiers constituant une séquence non décroissante, et vérifiant par conséquent:
a₁ <= a₂ <= a₃ <= ... <= a₉ <= s ;
2°) Calculer pour chaque liste obtenue le nombre d'arrangements correspondant, c.a.d. le nombre (N_(s)) de listes non ordonnées possibles, compte tenu du nombre de termes identiques présents; je ne suis pas familier de ce genre de problème, mais en y regardant de plus près, le résultat s'est révélé relativement simple;
3°) Faire la somme de tous les effectifs trouvés.
...
Je viens de programmer cela en Pascal, et c'est un peu lourd (neuf boucles imbriquées, alternant avec 8 instructuions conditionnelles). A partie de S = 100, mon portable équipé de Win7x64 me laisse le temps d'aller prendre une bière à la brasserie du coin. Y a-t-il un volontaire pour monter à 270 ? Prévoir du liquide, pour payer les consommations.

Smax / Nbre listes croissantes / Nbre total de listes
_ 0_ _ _ _ _ _ _1_ _ _ _ _ _ _ _ _ _1
_ 1_ _ _ _ _ _ _2_ _ _ _ _ _ _ _ _ 10
_ 2_ _ _ _ _ _ _4_ _ _ _ _ _ _ _ _ 55
_ 3_ _ _ _ _ _ _7_ _ _ _ _ _ _ _ _220
_ 4_ _ _ _ _ _ 12_ _ _ _ _ _ _ _ _715
_ 5_ _ _ _ _ _ 19_ _ _ _ _ _ _ _ 2002
_ 6_ _ _ _ _ _ 30_ _ _ _ _ _ _ _ 5005
_ 7_ _ _ _ _ _ 45_ _ _ _ _ _ _ _11440
_ 8_ _ _ _ _ _ 67_ _ _ _ _ _ _ _24310
_ 9_ _ _ _ _ _ 97_ _ _ _ _ _ _ _48620
_10_ _ _ _ _ 138_ _ _ _ _ _ _ _92378

_20_ _ _ _ 2 291_ _ _ _ _10 015 005
_30_ _ _ _18 115_ _ _ _ 211 915 132
_40_ _ _ _94 760_ _ _ 2 054 455 634
_50_ _ _387 666_ _ _ 12 565 671 261
_60_ _1 249 642_ _ _ 56 672 074 888
_70_ _3 572 052_ _ _205 811 513 765
_80_ _9 127 325_ _ _635 627 275 767
_90_ 21 312 056_ _1 731 030 945 644
100_ 46 208 882_ _4 263 421 511 271

Je me demande après coup si ce sujet n'est pas un lapin pour faire ramer les intervenants et leurs machines - ou tout au moins les étudiants informaticiens, tant l'énoncé paraît artificiel; une recherche sur le web montre qu'il s'agit tout simplement de la 10^me colonne du triangle de Pascal, beaucoup plus rapidement calculable par récurrence.
Ce que Prof a très bien vu; comme quoi il faut toujours réfléchir avant de foncer.
Je ne regrette cependant pas de m'être investi dans ce programme, qui contenait des éléments inhabituels, et me donnait l'occasion de tester le nouveau logiciel (Virtual Pascal), installé depuis trois semaines.

Consulter évidemment l'incontournable encyclopédie en ligne des suite entières:
https://oeis.org/search?q=1%2C10%2C5...age=&go=Search

http://oeis.org/wiki/Simplicial_polytopic_numbers

http://www.trans4mind.com/personal_d...edTriangle.htm