Discussion :

[arrangement]

Bjr à tous,
J'aimerais me faire aider sur la question suivante: Je pars de la série suivante de 114 nombres:

Code Texte :

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
7
286
200
176
120
165
206
75
129
109
123
111
43
52
99
128
111
110
98
135
112
78
118
64
77
227
93
88
69
60
34
30
73
54
45
83
182
88
75
85
54
53
89
59
37
35
38
29
18
45
60
49
62
55
78
96
29
22
24
13
14
11
11
18
12
12
30
52
52
44
28
28
20
56
40
31
50
40
46
42
29
19
36
25
22
17
19
26
30
20
15
21
11
8
8
19
5
8
8
11
11
8
3
9
5
4
7
3
6
3
5
4
5
6

Je cherche à savoir :

1. Combien de combinaisons de 28 nombres chacune l'on peut former à partir de cette série des 114 nombres.
2. Et à trier, parmi ces possibilités les séries de 28 nombres dont la somme est 1105.

Merci pour votre aide.

[tbc92]

Tu parles de combinaisons... et a priori, c'est le bon terme.
Si tu utilises un tableur, et tu tapes =combin(114,28), tu auras ta réponse... c'est un nombre avec 27 chiffres !

Dans ce décompte, on considère que la combinaison (286,200,176,120, ...) et (200,286,176,120, ...) ça compte pour une seule combinaison (l'ordre des termes ne compte pas).

Ahh , non, c'est moins que ça.
Tu as des doublons dans ta liste, le nombre 8 par exemple apparaît 5 fois.
Et j'imagine que si on prend la combinaison (200,286, 176,8 , ... ) avec le 8 qui vient de la ligne n° 102, ou la même chose mais avec le 8 de la ligne n°98, c'est pareil, il faut compter ça comme une seule combinaison. Le calcul est un peu compliqué... On devrait tomber vers un nombre à plus de 20 chiffres (?)

Lister toutes les combinaisons qui donnent une somme de 1105.
J'ai peur qu'il y en ait beaucoup !
La somme de tes 114 nombres donne un total 6236. Si on prend 28 nombres au hasard parmi ces 114, on arrive 'statistiquement' à un total proche de 6236*28/114=1531 ; C'est un peu plus grand que ton total de 1105, mais pas si grand que ça.

Eliminons les 14 nombres les plus grands, il nous reste 100 nombres, et la somme de ces 100 nombres donne un total de 3929
Si on prend 14 nombres au hasard parmi ces 100 nombres, on tombe 'statistiquement' sur un total proche de 3929*28/100 = 1100. On peut tomber sur un nombre de l'ordre de 600, si on est très malchanceux, ou de l'ordre de 1600, si on est très malchanceux dans l'autre sens... mais on va très souvent tomber dans cet intervalle.
Donc, à la grosse louche, on va tomber une fois sur 1000 sur le nombre visé, le 1105. (beaucoup plus que 1 fois sur 1000 en vrai)
Il y a Combin(100;14)=5*10^24 façons de choisir 28 nombres parmi 100, et 1 fois sur 1000, ça donne le nombre voulu 1105. ( Moins que ça, parce qu'on a nos doublons )
Et j'ai exclu les 14 nombres les plus grands de ta série, il faut ajouter à ce total les combinaisons avec au moins un nombre parmi ces 14.

Trouver le nombre précis de combinaisons qui donnent 1105 est infaisable mathématiquement. Informatiquement, les compter est envisageable, mais ça va être très long, et le nombre obtenu sera de toutes façons énorme. Un nombre à 15 chiffres ou plus.

Et créer un fichier avec toutes ces combinaisons... ce sera un fichier assez énorme !

[CosmoKnacki]

et le nombre obtenu sera de toutes façons énorme

Pas si sûr, car même si le nombre de combinaisons avec une somme proche de 1105 est important, je pense que la contrainte d'une valeur exacte est fortement discriminante. Autrement dit, il est incertain de se faire une idée du nombre de combinaisons répondant au critère en se basant sur une approximation faite sur un intervalle de sommes proches de la valeur recherchée.
Il ne faut pas non plus négliger les nombres redondants: 16 en double, 5 en triple, 1 quadruple et 2 quintuples.
Après pour la manière de procéder, c'est une autre affaire.

Concernant la première question, celle du dénombrement, ça doit être possible de trouver une formule générale du nombre de combinaisons de k éléments pour n éléments avec un certain nombre de double, triple, quadruple, etc., en tâtonnant et en résonnant par récurrence pour la prouver, à vue de nez ça à l'air fastidieux mais pas impossible.

[tbc92]

Sans la contrainte 'somme égale à 1105', oui, on peut faire un calcul précis, mais c'est très fastidieux. Et je ne sais pas trop quel est ton besoin, mais vu l'ordre de grandeur, qu'on arrive à 10^18 ou 10^20 ... je ne pense pas que ça change la face du monde.

L'approximation sur la contrainte 'somme=1105'

Je me limite aux 100 nombres les plus petits.
On prend 28 nombres au hasard parmi ces 100 nombres les plus petits. En moyenne la somme donne un nombre proche de 1100.

J'ai minimisé en disant qu'une fois sur 1000, on tomberait sur 1105 : on a 1000 résultats possibles, en toute première approximation, chaque résultat apparaît une fois sur 1000 .... mais en vrai, on a une gaussienne, et les résultats proches du centre ont une proba plus élevée que les résultats extrêmes.
Je t'invite à faire l'expérience, c'est assez facile à programmer.
Répète l'expérience 'tirer 28 nombres au hasard parmi ces 100 nombres' 1 Million de fois, pour vérifier si c'est réaliste ou pas , et compte combien de fois on obtient chacun des nombres 500,501, ... 1105, ... 1500...

Par contre, j'avais sous-estimé le nombre de doublons, et là, on peut diviser en gros par 100.

[Flodelarab]

Bonjour

Je déverse en vrac. Comprenne qui peut.

Parmi les 114 nombres, on constate ceci :

Code bash :

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

awk '{tab[$1]++;} END{t=0;for (y=1;y<=5;y++) for (i in tab) if (tab[i]==y) n[y]++; for (i in n) print i,n[i];}' fichier.txt

Code :

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

1
2
3
4
5
1 53                                                                                                                                                                          
2 16                                                                                                                                                                          
3 5                                                                                                                                                                           
4 1                                                                                                                                                                           
5 2

Cela signifie qu'il y a, par exemple, 5 nombres en quantité 3.

Code bash :

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

1
2
echo -n "echo {0";for ((i=1;i<=53;i++));do echo -n ",$i";done; echo -n "}\\ {0";for ((i=1;i<=16;i++));do echo -n ",$i";done; echo -n "}\\ {0";for ((i=1;i<=5;i++));do echo -n ",$i";done; echo -n "}\\ {0";for ((i=1;i<=1;i++));do echo -n ",$i";done; echo -n "}\\ {0";for ((i=1;i<=2;i++));do echo -n ",$i";done; echo "}§"
echo {0,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}\ {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}\ {0,1,2,3,4,5}\ {0,1}\ {0,1,2}§ | sed -z 's@§ @\n@g;s@§@@'| awk '($1+2*$2+3*$3+4*$4+5*$5==28)' | tee /tmp/floschema.txt

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
0 1 4 1 2
0 2 5 1 1
0 3 4 0 2
0 4 2 1 2
0 4 5 0 1
0 5 3 1 1
0 6 2 0 2
0 6 4 1 0
0 7 0 1 2
(...)
23 0 0 0 1
23 1 1 0 0
24 0 0 1 0
24 2 0 0 0
25 0 1 0 0
26 1 0 0 0
28 0 0 0 0

Cela signifie, par exemple, qu'on peut tirer 24 nombres en quantité 1 et 2 en quantité 2. Ce qui donne bien 28 nombres. Mais aussi 24 nombres en quantité 1 et 1 en quantité 4. Cela donne 28 nombres également.

Code python :

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
exec(open('/home/flodelarab/combi.py').read())
total = 0
qte=[53,16,5,1,2]
dispo=[0,0,0,0,2]
for i in range(3,-1,-1):
    dispo[i]=qte[i]+dispo[i+1]
print(qte)
print(dispo)
 
with open("/tmp/floschema.txt", "r") as f:
    fic = list()
    for line in f:
        if "#" in line:
            # on saute la ligne
            continue
        data = line.split()
        for i in range(5):
            data[i]=int(data[i])
        partiel=1
        pris=0
        for i in range(4,-1,-1):
            partiel *= nCp(dispo[i]-pris,data[i])
            pris += data[i]
        print(data,' ',pris,partiel)
        total += partiel
print('Total : ',total)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
[53, 16, 5, 1, 2]                                                                                                                                                             
[77, 24, 8, 3, 2]                                                                                                                                                             
[0, 1, 4, 1, 2]   8 85                                                                                                                                                        
[0, 2, 5, 1, 1]   9 3264                                                                                                                                                      
[0, 3, 4, 0, 2]   9 12240                                                                                                                                                     
[0, 4, 2, 1, 2]   9 38760                                                                                                                                                     
(...)
[24, 2, 0, 0, 0]   26 7114921083802497373200
[25, 0, 1, 0, 0]   26 626937973761147594624
[26, 1, 0, 0, 0]   27 3689288845594445460672
[28, 0, 0, 0, 0]   28 782835210292031251300
Total :  38375006427713952423869

Cela signifie qu'il y a précisément 38375006427713952423869 tirages différents de 28 nombres parmi ces 114.

Notez bien que si un nombre est en quantité 5, il peut en fournir 2 aussi.
Notez aussi que combi.py est juste un fichier pour des fonctions combinatoires comme nCp(n,p) qui ne fait que calculer la combinaison de p parmi n.

[arrangement]

Merci tout d'abord à tous les contributeurs . Je ne suis pas spécialiste mais j'ai pu grosso modo suivre le fil du raisonnement des uns et des autres. En fait, je soupçonnais un nombre astronomique de séquences de 28 nombres chacune. Je suppose que ces possibilités devraient décroître de façon très importante en introduisant une nouvelle contrainte que voici: on ne retient plus que les séquences de 28 nombres dont le total est 1105, ET uniquement lorsque ces nombres se suivent dans la série des 114 nombres. Ca revient à "extraire" des paquets séquentiels dans la série. Je pense qu'en procédant par test ( tri sous forme d'arbre ); les combinaisons de ce type ne devraient pas dépasser un ordre de grandeur à échelle humaine. Si je ne me trompe pas , cela ramènerait la série de nombres à 88 au lieu de 114 car à partir de ce rang, on n'a plus de séquence à 28 nombres qui se suivent. Cela nous éloignerait bien loin des 10 puissance 24! Mais ce travail sied très bien à la machine mais pas aux humains. J'espère tomber sur la toile sur un puissant logiciel de calcul de ce genre .
Merci encore une fois.
Cordialement
PS: J'ai renvoyé un message apparenté hier soir, comme je ne l'ai pas retrouvé sur le forum , je le balance de nouveau dans l'espoir d'une piste de solution ou d'un algorithme pertinent.

[tbc92]

Si tu ajoutes la contrainte 'les 28 nombres retenus doivent se suivre dans la liste initiale', alors ça va très vite.
Il y a seulement 87 groupes à tester, et miracle, un de ces 87 groupes convient :
54
53
89
59
37
35
38
29
18
45
60
49
62
55
78
96
29
22
24
13
14
11
11
18
12
12
30
52

En fait, ce n'est pas un miracle... je disais précédemment que sous certaines conditions, on avait environ 1 chance sur 200 qu'un groupe donne 1105 ; donc, en prenant 87 groupes, le fait qu'un de ces groupes donne 1105 est assez chanceux, mais pas miraculeux.

[Guesset]

Bonjour,

Proposition au doigt mouillé :

• Commencer par trier les valeurs par ordre croissant.
• Compter la somme de blocs compacts de 28 valeurs (consécutives donc). 1 à 28, 2 à 29, 3 à 30 etc. Il y a moins de 86 sommes et cela ne nécessite pas de double boucle sauf pour l'initialisation du premier bloc.
• S'arrêter dès que la somme dépasse 1105. Cela donne deux informations : la plus petite valeur doit être à un indice <= 44 (base 1) et la plus grande à un indice >= 72.
• Balayer de 1 à 44, les indices pour la valeur basse et de 72 à 114 les indices pour la valeur haute.
• On a alors le même problème à résoudre pour les 26 valeurs restant à trouver en commençant après l'indice de la valeur choisie pour la valeur basse et celui de la valeur choisie pour la valeur haute pour une somme de : 1105 - ces deux valeurs.
• Le pré-calcul initial pour 28 valeurs consécutives permet d'engendrer les limites pour les collections de 26, 24,..., 6, 4 valeurs consécutives à moindre coût (2 est inutile puisqu'il n'en alors reste que deux à choisir )
• Et ainsi de suite.

Sauf erreur, le nombre d'itérations est important mais sans commune mesure avec l'anarchie de la distribution initiale (entre 20 à 30 000) ce qui reste petit pour les machines actuelles.

Le principe sous-jacent est, qu'avec des valeurs triées par ordre croissant, si on remplace une valeur d'un bloc compact par une valeur plus petite hors bloc la somme sera diminuée. Cela sera donc interdit si ce bloc compact est juste en dessous de la somme cible, ce qui fixe l'indice minimal de la valeur maximale d'une collection.
Il en va de même pour le bloc compact dont la somme est juste au dessus de la cible, l'indice maximal de la valeur minimale d'une collection ne peut alors être supérieure ou égale à l'indice du bloc compact précité.

En supposant que le problème n'est pas plus trivial

Salutations

[tbc92]

@flodelarab : tu as oublié la contrainte : un lot doit contenir 28 nombres.
@Guesset : je n'ai rien compris à ton message.
En fait, l'objectif n'est pas totalement clair.
1) recenser toutes les combinaisons de 28 nombres dont la somme va donner 1105 : énormément de solutions, pas très réaliste. On va en faire quoi après ?
2) Compter toutes les combinaisons de 28 nombres dont la somme va donner 1105 : le nombre va être très grand.
3) Trouver des combinaisons de 28 nombres dont la somme va donner 1105 : en donnant un petit coup de pouce à la chance, on va facilement trouver plein de solutions.

[Guesset]

Bonjour tbc92,

...Donc, à la grosse louche, on va tomber une fois sur 1000 sur le nombre visé, le 1105...
Et créer un fichier avec toutes ces combinaisons... ce sera un fichier assez énorme !

Si on calcule la probabilité d'une gaussienne, P(1105) = f(1105)dx (avec dx = 1 car on cherche la valeur exacte) on trouve, sauf erreur, quelque chose de l'ordre de 10^-16 ce qui est moins optimisme que 10^-3 mais laisse quand même environ 10¹⁰ solutions ce qui confirme le coté irréaliste : il faut au moins 15 octets par solution soit de l'ordre de 0.15 To pour l'ensemble !

Salut

[tbc92]

Je me situais dans un univers restreint : on considère uniquement les 100 plus petits nombres, ceux entre 3 et 111. Si je prends 28 nombres au hasard dans cet ensemble, j'arrive en moyenne à 1100 (La somme de ces 100 nombres multipliée par 0.28).
Si on tire au hasard 28 nombres dans cet univers, et qu'on est très malchanceux, on peut arriver à 218 (les 28 plus petits) ou 2255 (les 28 plus grands). Mais ces 2 cas vraiment extrêmes, et très rares. On va tomber très souvent sur un nombre entre 500 et 1500.
En admettant que ces 1000 résultats (500 à 1500) sont équiprobables, chacun a une probabilité 1/1000 d'arriver. Mais en fait, les résultats proches de la moyenne sont plus probables.... donc 1/100 ou 1/200 environ.

Le sous échantillon que j'étudie (les combinaisons qui n'ont aucun des 14 plus grands nombres) compte 5x10^24 combinaisons, contre 4x10^26 pour le total (Combin(100;28) vs Combin(114,28)) : Donc, quand on rapporte ça à l'univers complet, il y a environ 1 combinaison sur 10000 qui mène à 1105.

[Guesset]

Bonjour tbc92,

...Le sous échantillon que j'étudie (les combinaisons qui n'ont aucun des 14 plus grands nombres) compte 5x10^24 combinaisons, contre 4x10^26 pour le total (Combin(100;28) vs Combin(114,28)) : Donc, quand on rapporte ça à l'univers complet, il y a environ 1 combinaison sur 10000 qui mène à 1105.

Mea culpa, j'ai calculé avec les pieds en oubliant le coefficient 28 . En corrigeant cela j'obtiens 1/11 794 ce qui est proche des 1/10 000 que tu cites.

Il y a quand même quelque chose à prendre en compte. Nous ne sommes pas dans une distribution continue et certaines valeurs peuvent être interdites. Par exemple, en transformant toutes les valeurs impaires en valeurs paires alternativement par excès et défaut, la distribution garde la même moyenne et une valeur type à environ 2/1000 de la précédente ce qui donne quasiment la même probabilité pour 1105 alors que cette valeur n'est plus possible. Il y a des trous dans la distribution.

Les 114 valeurs comportent 60 valeurs paires et 54 valeurs impaires. Seulement la moitié aura un nombre impair de valeur impaires. J'aurais donc tendance à considérer que la probabilité réelle est plutôt du 1/23 588 ce qui ne change en pas le coté irréaliste du stockage des résultats.

Salut

[tbc92]

Pourquoi veux tu diviser par 2 pour ces questions de parité ? Si les 114 nombres étaient tous pairs, (ou tous impairs) évidemment, oui, il n'y aurait pas de solution.

Je dis qu'il y a environ 4x10^22 combinaisons qui donnent 1105, à peu près pareil pour 1106, à peu près pareil pour 1107, etc. Et ça monte petit à petit, pour atteindre à peu près 2x10^24 pour les nombres proches de 1531 (la valeur moyenne quand on prend 28 nombres parmi les 114 proposés). Et la somme de tous ces nombres donne notre total , 4x10^26.
Donc il y a bien la moitié des combinaisons qui donnent un nombre pair. Pas de raison de diviser par 2.

Autre façon de voir le problème : on a un total de 4x10^26. On doit dispatcher ce total sur les nombres entre 300 et 6000 ... c'est à dire les différents totaux possibles, (j'ai exclu les extrêmes, qui restent possibles, mais très très peu probables). On doit donc dessiner une gaussienne, avec ces 5700 valeurs possibles, et regarder la hauteur obtenue pour chaque barre.

Evidemment, dans tout ça, on fait l'impasse sur les valeurs qui se répètent. On considère que la combinaison 286.7a.54.7b.11a et la combinaison 286.7c.54.7b.11b... ce sont 2 combinaisons différentes.
Si on considère ça comme des doublons, il faut diviser tout ça par un facteur proche de 100 (à vérifier). Et comme les nombres multiples sont plutôt les petits nombres, il faut diviser par un facteur plus grand pour les nombres proches de 1000 ou 1100.

Si on avait un seul nombre impair parmi les 114 ... on aurait un biais. On tire 'seulement' 28 nombres sur les 114. On aurait donc environ 1 quart des tirages avec une somme impaire, au lieu de la moitié comme on a ici. Et donc il faudrait appliquer un coefficient 1/2

[Guesset]

Bonjour,

Même si le problème du PO s'est avéré bien plus simple que ne le supposait l'exposé initial (87 sommes en 114 opérations simples : 28 additions pour avoir Sum₀, puis 86 opérations Sum_i = Sum_i-1 - V[i-1] + V[i+27] pour i = 1 à 86), je suis resté sur le problème plus générique car plus intéressant.

J'ai écrit un petit programme de simulation de tirage qui donne ceci :

Première chose que l'on remarque, la valeur moyenne est proche de 1581 et non de 1532. C'est surprenant mais nous ne sommes pas dans le cas de variables indépendantes.

Seconde chose, consécutive de la première, le taux de solutions 1105 est plus faible qu'imaginé initialement : 1/58000.

Ensuite les irrégularités persistent, même si la mise à l'échelle de l'écran les fait progressivement disparaître visuellement. Leurs valeurs absolues tendent à croitre tandis que leur valeurs relatives diminuent. Ainsi chercher le maximum H_max de la courbe est assez difficile car la détection sur le sommet, quasi plat est très sensible aux irrégularités.

La recherche de l'écart type à 0.6 H_max gomme cette imprécision car les pentes sont fortes. On peut donc en déduire une Médiane beaucoup plus proche de l'abscisse du sommet théorique. Il faut atteindre environ 200 millions de tirages pour que la médiane (rapidement stable) coïncide avec l'abscisse du maximum (et il y a des soubresauts).

Ci-joint l'application pour Windows : Sum1105.7z. Les sources sont disponibles si cela intéresse quelqu'un.

Quand la souris est sur l'écran, on peut déplacer la verticale d'analyse en maintenant le bouton gauche appuyé ou avec les flèches du clavier. Il y a 3 modes de calcul. Un par un pour voir les blocs de 28 valeurs générés, lent pour voir la construction progressive de la courbe, rapide pour progresser rapidement en n'affichant que le résultat après n calculs. Il n'y a pas de défilement panoramique de l'écran : les extrêmes restent donc inaccessibles.

Salutations