Discussion :

[wiwaxia]

... (*) @wiwaxia : Pour ta solution avec les fonctions affines, j'espère que tu comprends mon point de vue quand je dis que c'est biaisé Mes deux arguments principaux pour ça sont le fait qu'on retrouve la valeur min et max la plupart du temps, et le fait de choisir entre 3 fonctions affines qui amène à 3 "catégories" de solutions qui ne se mélangent pas forcément bien.

Je comprend bien l'objection, et la réticence suscitée l'accumulation des valeurs extrêmes.
La difficulté provient de l'écart considérable séparant la distribution uniforme sur [0 ; 1[ des valeurs retournées par une fonction pseudo-aléatoire, et la distribution très resserrée exigée par l'énoncé:

Vmoy/2 ≤ Vmin ; Vmax ≤ 3.Vmoy/2 ,

qui n'est fortuitement réalisée que pour une faible proportion des tirages (~1.5 %).

Elle provient aussi de l'absence, dans l'énoncé, de toute indication concernant le type de calculs ou la densité de probabilité des valeurs obtenues, laissant ainsi libre cours à l'inventivité de chacun.

Pour en revenir à la difficulté initialement évoquée, le tirage d'une valeur aléatoire supplémentaire (Kal) permet de passer à une seconde suite finie de 10 valeurs réelles:

Y_j = Xmoy + Kal*(X_j - Xmoy)

à partir de laquelle on peut recalculer (Ymin, Ymoy, Ymax), ainsi que les rapports Rmin = Ymin/Ymoy et Rmax = Ymax/Ymoy ; le cas idéal se retrouve alors réalisé beaucoup plus souvent (55 % des cas):

À ce stade, on pourrait ne plus tenir compte des tirages défavorables, désormais minoritaires.

[wiwaxia]

Sur le fond, il faut faire simple.
Le petit programme suivant
- effectue 10 tirages aléatoires sur un domaine de valeurs entières allant de 20 à 60 par la relation E = 20 + Random(41) ,
- calcule la somme correspondante, et
- ajoute ou retranche une unité autant de fois qu'il le faut à l'un des termes pris au hasard, afin de ramener la somme à la valeur souhaitée (400).

Code Pascal :

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
115
116
117
118
119
120
 PROGRAM XXX;
 
 USES Crt, E_Texte, U_Math;
 
 CONST Npoint = 10; Seuil = 400;
 
 TYPE Tab_NE = ARRAY[1..Npoint] OF Word;
 
 VAR Somme_1, Somme_2: Word;
     Lst_E1, Lst_E2: Tab_NE;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 Correction de la suite
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Aff_L2(VAR L_1, L_2: Tab_NE);// Affichage de la 2nde liste
   CONST C1 = 5; L1 = 7; u = 4;
   VAR j: Byte;
   BEGIN
     E(0015); Wt(C1, L1, 'Lst_E2 = ');
     FOR j:= 1 TO Npoint DO
       BEGIN
         IF (L_1[j]=L_2[j]) THEN E(0010) ELSE E(0013);
         Write(Lst_E2[j]:u);
       END;
     E(0015); Write('     Somme_2 = ');
     E(0012); Write(Somme_2:u);
 
     Wt(3, 1, 'Å'); Wt(74, 9, 'Å')      // Rep‚rage de d‚coupe d'image ‚cran
   END;
 
 PROCEDURE Calc_S(VAR L_: Tab_NE; VAR S_: Word);
   VAR j: Byte; s: Word;
   BEGIN
     s:= 0; FOR j:= 1 TO Npoint DO Inc(s, L_[j]);
     S_:= s
   END;
 
 PROCEDURE Corr_2(S_1: Word; VAR L_1, L_2: Tab_NE);
   VAR i, j, k: Word; Liste: Tab_NE;
   BEGIN
     Liste:= L_1;
     FOR i:= 1 TO (Seuil - S_1) DO
       BEGIN
         REPEAT
           j:= Random(Npoint); k:= Liste[j + 1]; Inc(k);
         UNTIL (k<61);
         Liste[j + 1]:= k
       END;
     L_2:= Liste
   END;
 
 PROCEDURE Corr_1(S_1: Word; VAR L_1, L_2: Tab_NE);
   VAR i, j, k: Word; Liste: Tab_NE;
   BEGIN
     Liste:= L_1;
     FOR i:= 1 TO (S_1 - Seuil) DO
       BEGIN
         REPEAT
           j:= Random(Npoint); k:= Liste[j + 1]; Dec(k);
         UNTIL (k>19);
         Liste[j + 1]:= k
       END;
     L_2:= Liste
   END;
 
 PROCEDURE Correction_L(S_1: Word; VAR L_1, L_2: Tab_NE);
   CONST C1 = 15; L1 = 5;
   BEGIN
     IF (S_1=Seuil) THEN BEGIN
                           E(0011); Wt(C1, L1, 'Somme exacte'); L_2:= L_1
                         END
                    ELSE IF (S_1>Seuil) THEN Corr_1(Somme_1, Lst_E1, Lst_E2)
                                        ELSE Corr_2(Somme_1, Lst_E1, Lst_E2)
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 Tirage des 10 entiers
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Aff_L1;                      // Affichage de la 1re liste
   CONST C1 = 5; L1 = 3; u = 4;
   VAR j: Byte;
   BEGIN
     E(1015); Wt(C1, L1, 'Lst_E1 = ');
     E(0010); FOR j:= 1 TO Npoint DO Write(Lst_E1[j]:u);
     E(0015); Write('     Somme_1 = ');
     E(0012); Write(Somme_1:u)
   END;
 
 PROCEDURE Tirage(VAR S_: Word; VAR L_E: Tab_NE);
   VAR j:Byte; k, s: Word;
   BEGIN
     Randomize; s:= 0;
     FOR j:= 1 TO Npoint DO BEGIN
                              k:= Random(41); Inc(k, 20);
                              L_E[j]:= k;     Inc(s, k)
                            END;
     S_:= s
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 Programme principal
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 VAR Tch: Char;
 
 BEGIN
   REPEAT
     Tirage(Somme_1, Lst_E1);               Aff_L1;
     Correction_L(Somme_1, Lst_E1, Lst_E2); Calc_S(Lst_E2, Somme_2);
     Aff_L2(Lst_E1, Lst_E2);                Tch:= ReadKey
   UNTIL Tch IN ['1'..'9']
 END.

Exemples:

Il serait intéressant de calculer la densité de probabilité des valeurs sur le domaine [20 ; 60].

[Guesset]

Bonjour,

Je ne suis pas sûr du tout que cette démarche, assimilable à celle du pendu, garantisse une probabilité égale d'atteindre chacune des 97 809 616 solutions car les ajustements ne sont pas aléatoires.

Mais peut être n'est-ce pas important.

Salutations.

[mach1974]

Super … et on optimise quoi exactement ? Juste comme ça … ce que tu proposes c'est bien, mais c'est du vent quand le cardinal de l'ensemble des solutions est de l'ordre de 10⁹. Et tu n'as pas tort de parler des GF (enfin juste les deux mots là hein), car comment crois-tu qu'on arrive à évaluer la taille de l'ensemble des solutions ?



À nouveau … quelle est la taille qu'aurait ce fichier ? Comment génère-t-on les solutions du fichier ?

Je ne sais pas si vous vous rendez compte de la complexité mémoire de vos trucs «simples».

Le principal but de mon message était surtout de montrer qu'il faut penser le problème avant de proposer une solution, sachant que c'est souvent celui qui pose la question qui a la pire solution en tête.
Mais au final, si c'est un petit toy project ce sera certainement la solution de TBC92 la plus viable.

lol avec l'algo du simplexe on optimise une fonction A+B+C+D+E+F+G+H+I+J-400

avec A <borne max etc .....
Avec la méthode des matrices en 10 itérations c'est fini

donc ce n'est pas du vent

[Guesset]

Bonjour Flodelarab,

...Le fichier est tellement gros que ce n'est même pas rapide de piocher dedans. ...

J'avais eu le même problème, je ne stockais pas dans un fichier mais affichais dans un memo. Ca tient mais les conversions int > str plombaient singulièrement les délais. C'est pourquoi je me contente de capter une solution selon un rang fixé par l'utilisateur ou aléatoire. Je ne conserve rien et recalcule tout si besoin. Un peu plus d'une demi seconde n'épuise pas ma patience.

Les solutions de choix aléatoires sous contraintes sont plus efficaces. Mais celles qui sortent toutes les configurations permettent entre autres de savoir combien il y en a vraiment, ce que les estimations n'approchaient qu'à 20% dans le meilleurs des cas.

Salut

[WhiteCrow]

lol avec l'algo du simplexe on optimise une fonction A+B+C+D+E+F+G+H+I+J-400

avec A <borne max etc .....
Avec la méthode des matrices en 10 itérations c'est fini

donc ce n'est pas du vent

Je ne dis pas que c'est du vent, ah si … ^_^ c'est bien ce que je dis

Donc voilà pourquoi je le dis :

Tu proposes d'utiliser une méthode complexe d'optimisation, le simplexe. Une dizaine d'itération suffit … pour arriver à quoi ? une solution ? une ensemble de solutions ? toutes les solutions ? Un ensemble de solutions «aléatoires» ?

Autant commencer simplement avec une solution ordonnée genre le tuple (40,40,40,40,40,0,0,0,0,0) si on accepte les solutions avec des éléments non distincts, ou le tuple (40,39,38,37,36,4,3,2,1,0) si les éléments doivent être distincts. On dispose d'algorithmes loopless simples et linéaires en temps en fonction du nombre d'éléments pour passer d'une solution à une autre en ordre colex …
Si les éléments doivent être distincts alors il suffit (ok c'est facile à dire ^_^) de choisir «aléatoirement» une solution parmi toute les solutions, si les éléments ne doivent pas être distincts alors il faut au minimum avoir un cumul du nombre de combinaisons que l'on peut obtenir à partir d'un tuple donné.

Il me semble, mais je peux me tromper, que l'implémentation sera bien plus simple … même si je rappelle tout de même que : «Mais au final, si c'est un petit toy project ce sera certainement la solution de TBC92 la plus viable.».

[AbsoluteLogic]

Tu proposes d'utiliser une méthode complexe d'optimisation, le simplexe. Une dizaine d'itération suffit … pour arriver à quoi ? une solution ? une ensemble de solutions ? toutes les solutions ? Un ensemble de solutions «aléatoires» ?

Je rajoute à ça que le simplexe pour moi consiste à maximiser ou minimiser un fonction, pas à la faire converger vers 0. Donc il nous retournerait toujours du (20,...,20) ou (60,...,60).
Et donc oui, tout le problème est d'avoir une bonne distribution des résultats, d'où mon post suivant.

Mais au final, si c'est un petit toy project ce sera certainement la solution de TBC92 la plus viable.

Bon, sur ce point là, j'avoue que je considère que ça va plus loin que ça C'est un sujet intéréssant, et qu'on peut retrouver dans des contextes variés, donc c'est bien d'y répondre dans le cas général. D'ailleurs j'imagine que e0x1n est parti depuis longtemps

[AbsoluteLogic]

Il serait intéressant de calculer la densité de probabilité des valeurs sur le domaine [20 ; 60].

Effectivement, c'est le meilleur moyen de comparer les solutions en terme de "distribution" ^^ Voici donc les distributions (la distribution est calculée en faisant la moyenne sur 1000000 tirages, à part pour la courbe rouge où j'ai parcouru toutes les solutions) :

• En bleu : solution de tbc92 (post #2). J'ai envie de dire que c'est la distribution de référence puisqu'on ne fait aucun choix arbitraire (mais évidemment ça dépend du besoin de l'utilisateur). Au passage, j'en profite pour confirmer qu'avec cette solution et avec ces paramètres, on a environ 99% de rejet comme évoqué .
• En rouge : solution de Flodelarab (post #6). Courbe lisse parce ce n'est pas un tirage aléatoire mais la moyenne de toutes les solutions triées. Si on parcourt toutes les solutions non triées, on devrait s'attendre à retrouver la distribution de référence. En tout cas, en considérant uniformément toutes les solutions triées, on voit qu'on favorise les valeurs "moyennes" au détriment des valeurs "limites". Et on a vu que considérer toutes les solutions non triées est... compliqué.
• En jaune: ma solution (post #8). Etonnamment je l'avoue, on retombe bien sur la distribution de référence. Il est très peu probable que les distributions soient égales, surtout que j'ai arbitrairement choisi une fonction exponentielle pour mon procédé. Mais en tout cas le résultat est très proche et donc plutôt satisfaisant.

En terme de performance, ça me prend 13s pour générer 1000000 de tuples avec ma solution contre 20s pour la méthode par rejet de tbc92. Ce n'est pas extraordinaire, mais on gagne avec cette solution "plus compliquée" surtout lorsque la contrainte est plus restrictive (cf comparaison post #20), et où la solution par rejet mettra trop de temps à trouver chaque solution.

@wiwaxia
J'ai mis tes solutions sur un graphe séparé pour ne pas encombrer le 1er graphe, et parce que les valeurs sont plus variées, donc j'aurais eu moins de précision.

• En bleu : distribution de reférence
• En rouge : distribution résultant de la solution du post #22. On retrouve pas mal les valeurs extrêmes, notamment parce que les valeurs proches du bord ont beaucoup de chance de s'accumuler sur le bord lors des corrections.
• En jaune: distribution résultant de la solution du post #15. Les valeurs extrèmes en force comme prévu. Je n'ai pas mis ta proposition d'amélioration post #21, notamment parce que je n'ai pas compris quel facteur appliquer. Un facteur aléatoire entre 0 et 1 ? Si c'est le cas alors je peux t'assurer que ça n'améliore pas la distribution :p

Aussi, on voit que ces deux solutions amènent plus un "plateau" sur les valeurs moyennes.


Je joins le code que j'ai utiliser pour générer les solutions. En C++ pour avoir de bonnes perfos, et pas documentée (j'ai déjà assez travaillé :p), donc c'est surtout si vous voulez vraiment regarder et que vous avez le courage
>>> main.cpp <<<

[WhiteCrow]

Ce qu'il faudrait mesurer, ou calculer, c'est la distribution des solutions pas des éléments des solutions. Car, au final, ce qui serait important d'exhiber est une équiprobabilité de tirage des tuples.

[AbsoluteLogic]

Ce qu'il faudrait mesurer, ou calculer, c'est la distribution des solutions pas des éléments des solutions. Car, au final, ce qui serait important d'exhiber est une équiprobabilité de tirage des tuples.

Oui, mesurer la distribution des "vecteurs" solutions plutôt que des valeurs serait théoriquement plus juste. Mais ça voudrait dire mesurer la fréquence de chacun de ces éléments qui sont environ au nombre de 1e14 (= (41^10)*0.01 car on a 41^10 solutions sans contrainte, et environ 99% de rejet avec contrainte). C'est inenvisageable. Mais je trouve quand même qu'on peut se fier à la distributions des valeurs, parce que je vois mal un algo amener les mêmes valeurs sans amener les mêmes vecteurs.

Pour ce qui est de "calculer", il s'agit donc d'énumérer les solutions selon les paramètres. Si quelqu'un est en mesure de le faire, ça faciliterait vraiment les choses.
D'ailleurs si on était en mesure de calculer la fréquence théorique d'une valeur selon les données du problème (ie la formule de P(x|s,n) la probabilité d'avoir x en 1ère valeur sachant qu'on veut atteindre la somme s en n valeurs), alors on pourra appliquer l'algo suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
Entrée: N le nb d éléments, S la somme voulue, xMin/xMax les limites voulues
Sortie: X un tableau de N éléments
s := S # somme restante
n := N # éléments restants
Pour i de 1 à N
  Pour x de xMin à xMax
    Calculer P(x|s,n)
  X[i] := valeur aléatoire selon la pondération des P(x|s,n)
  s := s - X[i] # On actualise la somme restante
  n := n - 1 # On actualise le nb d éléments restants

Pour revenir à la "mesure", si on ne peut pas calculer P(x|s,n) mais qu'on peut mesurer sa valeur pour toutes les entrées possibles (dans notre cas : 41 * 400 * 10 = 164000 valeurs), alors ce serait plus facile à stocker que la liste de toutes les solutions. Puisqu'on est en mesure d'énumérer les solutions triées, on peut mesurer exactement ses valeurs, et ça donne une nouvelle solution au problème qui donne la même distribution que "tirer uniformément dans la liste des solutions triées", mais de manière beaucoup plus performante et moins coûteuse en mémoire.
Tout ça fonctionne donc aussi pour générer des solutions non triées, mais pour ça il faudrait pouvoir mesurer les P(x|s,n) dans ce contexte.

[WhiteCrow]

Dans le cas où ce qui est demandé est un tuple de 10 entiers deux à deux distincts non nuls de ]0,40] dont la somme vaut 200, l'approche consistant à les générer tous les tuples ordonnés et à en tirer un aléatoirement fonctionne car ils ont tous la propriété d'avoir 10! permutations distinctes. Pour choisir aléatoirement plusieurs tuples distincts, l'approche la plus simple, me semble-t-il, est d'utiliser un fisher yates sur l'ensemble des tuples et d'en prendre le X premiers, quitte à repasser un fisher yates sur chacun des tuples pour donner un look plus «aléatoire».
Car au final, le demande du PO est bien d'obtenir plusieurs de ces tuples, c'est donc la distribution de ces ensembles de tuples qui est à tester.

Dans le cas où ce qui est demandé est un tuple de 10 entiers de [0,40] dont les éléments peuvent éventuellement être égaux et dont la somme vaut 200, il faut en plus de la génération ordonnée des tuples ordonnés conserver un cumul du nombre de permutations uniques de chaque tuple. Cela permet de choisir aléatoire un nombre qui correspondra à un tuple particulier. On ne peut plus vraiment utiliser le truc de l'approche précédente pour générer un groupe, on peut néanmoins conserver le fisher yates sur les tuples pour le look.

[Flodelarab]

Dans le cas des 10 nombres différents, on a 13 355 414 cas :

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
 20 21 22 23 24 56 57 58 59 60
 20 21 22 23 25 55 57 58 59 60
 20 21 22 23 26 54 57 58 59 60
 20 21 22 23 26 55 56 58 59 60
 20 21 22 23 27 53 57 58 59 60
 20 21 22 23 27 54 56 58 59 60
 20 21 22 23 27 55 56 57 59 60
 20 21 22 23 28 52 57 58 59 60
 20 21 22 23 28 53 56 58 59 60
 20 21 22 23 28 54 55 58 59 60
 20 21 22 23 28 54 56 57 59 60
 20 21 22 23 28 55 56 57 58 60
 20 21 22 23 29 51 57 58 59 60
 20 21 22 23 29 52 56 58 59 60
 20 21 22 23 29 53 55 58 59 60
 20 21 22 23 29 53 56 57 59 60
 20 21 22 23 29 54 55 57 59 60
 20 21 22 23 29 54 56 57 58 60
 20 21 22 23 29 55 56 57 58 59
 20 21 22 23 30 50 57 58 59 60
(...)
 34 35 37 38 40 41 42 43 44 46
 34 35 37 39 40 41 42 43 44 45
 34 36 37 38 39 40 41 42 43 50
 34 36 37 38 39 40 41 42 44 49
 34 36 37 38 39 40 41 42 45 48
 34 36 37 38 39 40 41 42 46 47
 34 36 37 38 39 40 41 43 44 48
 34 36 37 38 39 40 41 43 45 47
 34 36 37 38 39 40 41 44 45 46
 34 36 37 38 39 40 42 43 44 47
 34 36 37 38 39 40 42 43 45 46
 34 36 37 38 39 41 42 43 44 46
 34 36 37 38 40 41 42 43 44 45
 35 36 37 38 39 40 41 42 43 49
 35 36 37 38 39 40 41 42 44 48
 35 36 37 38 39 40 41 42 45 47
 35 36 37 38 39 40 41 43 44 47
 35 36 37 38 39 40 41 43 45 46
 35 36 37 38 39 40 42 43 44 46
 35 36 37 38 39 41 42 43 44 45

Si le premier tirage est aussi beau qu'on pouvait l'imaginer, le dernier ne l'est pas, car il n'existe aucune somme de dix entiers consécutifs qui fasse 400.

[tbc92]

Plutôt que mesurer la distribution des vecteurs, une solution est de mesurer la distribution des moments d'ordre 1, 2 , 3, 4 , et on peut s'arrêter là.

Moment d'ordre i = moyenne des xⁱ

Le moment d'ordre 1, c'est la moyenne des 10 nombres, c'est forcément 40. Fin.
Le moment d'ordre 2, c'est au facteur 10 près, la variance des 10 nombres. Est-ce que la variance sur les séries générées est globalement la même que la variance théorique.
Le moment d'ordre 3 : comme les outils de bidouillage proposés sont symétriques, on ne devrait avoir aucun problème sur cet indicateur.
Le moment d'ordre 4 : la moyenne des x⁴

Si les moments d'ordre 2 et 4 sont conformes aux valeurs théorique, alors jackpot.

[wiwaxia]

... Si le premier tirage est aussi beau qu'on pouvait l'imaginer, le dernier ne l'est pas, car il n'existe aucune somme de dix entiers consécutifs qui fasse 400.

Effectivement, mais il y a tout de même 2 séquences arithmétiques dont la somme vaut 400, restant dans les limites de l'énoncé, de raison r = 2k et de terme initial T₀ = 40 - 9k:

# k = 1: 31_33_35_37_39_41_43_45_47_49 ;
# k = 2: 22_26_30_34_38_42_46_50_54_58 .

;

[AbsoluteLogic]

Dans le cas où ce qui est demandé est un tuple de 10 entiers deux à deux distincts non nuls de ]0,40] dont la somme vaut 200, l'approche consistant à les générer tous les tuples ordonnés et à en tirer un aléatoirement fonctionne car ils ont tous la propriété d'avoir 10! permutations distinctes.

Effectivement, dans le cas de valeurs 2 à 2 distinctes, considérer toutes les solutions ordonnées donne la bonne distribution des solutions. Je remets mes belles courbes pour ce cas :

On remarque d'ailleurs un peu plus sur ce graphe que ma solution (Correcting with smooth function) est un peu biaisée, avec un peu plus de valeurs moyennes.

Plutôt que mesurer la distribution des vecteurs, une solution est de mesurer la distribution des moments d'ordre 1, 2 , 3, 4 , et on peut s'arrêter là.
[...]
Si les moments d'ordre 2 et 4 sont conformes aux valeurs théorique, alors jackpot.

Je refuse pas un critère de comparaison supplémentaire. Voici le résultat :

	Distribution des moments d'ordre 2 (somme des x2)	Distribution des moments d'ordre 4 (somme des x4)
Duplicata autorisés
Elements 2 à 2 distincts

On voit une claire différence pour le tirage parmi les solutions triées dans le cas des duplicata autorisés, et l'absence de différence (on ne voit pas la courbe) dans le cas des éléments 2 à 2 distincts.
Et on remarque une légère différence pour la solution de correction par fonction lisse, avec valeurs 2 à 2 distinctes ou pas.

[AbsoluteLogic]

Je me permets de faire encore un post puisque je pense avoir trouvé une nouvelle solution qui respecte parfaitement la distribution, tout en étant efficace avec des paramètres flexibles. Il s'agit de l'algorithme que j'avais évoqué au post #30. Il manquait "seulement" la formule énumérant le nombre de solutions pour des paramètres quelconques (valeur max / nb d'éléments / somme visée) :

D'ailleurs si on était en mesure de calculer la fréquence théorique d'une valeur selon les données du problème (ie la formule de P(x|s,n) la probabilité d'avoir x en 1ère valeur sachant qu'on veut atteindre la somme s en n valeurs), alors on pourra appliquer l'algo suivant :

Code :

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

1
2
3
4
5
6
7
8
9
10
Entrée: N le nb d éléments, S la somme voulue, xMin/xMax les limites voulues
Sortie: X un tableau de N éléments
s := S # somme restante
n := N # éléments restants
Pour i de 1 à N
  Pour x de xMin à xMax
    Calculer P(x|s,n)
  X[i] := valeur aléatoire selon la pondération des P(x|s,n)
  s := s - X[i] # On actualise la somme restante
  n := n - 1 # On actualise le nb d éléments restants

Il se trouve que quelqu'un de mon entourage avait croisé ce papier de CAMILA C. S. CAIADO et PUSHPA N. RATHIE dans lequel ils ont calculé la distribution de la somme de N entiers suivant une loi uniforme. Donc ils ont calculé P(sum(X)=s) pour un N (nb d'éléments) et un k (amplitude des valeurs) quelconques (formule (2.8) du papier). En multipliant par le nombre d'entrées possibles (i.e. k^N), on obtient une formule donnant le nombre de solutions selon des paramètres quelconques :

>> s : somme normalisée ( = somme voulue - xMin * N)
>> N : nombre d'éléments par tuple
>> k : amplitude des valeurs ( = xMax - xMin + 1)
A noter que le nombre de solutions commençant par un x donné, c'est le nombre de solutions pour N-1 et s-x.

J'ai donc pu tester cette solution (code C++) avec environ 100000 tuples générés par seconde en C++ avec les paramètres évoqués (10 valeurs entre 20 et 60). En tout cas lorsqu'on calcule à chaque fois la formule complètement. Si on réutilise les coefficients calculés (avec un cache), c'est encore 7 fois plus rapide.

Ensuite, si je continuais à me pencher sur le sujet, c'est pour avoir une solution qui marche avec des paramètres quelconques. En effet, avec les paramètres évoqués jusque là, cette solution n'est pas beaucoup plus performante que la manière brute (générer sans contrainte de somme et rejeter les mauvaises sommes). Mais c'est notamment lorsque la contrainte devient plus contraignante (somme qui n'est pas la moyenne des valeurs) que la solution brute se dégrade alors que cette nouvelle solution maintient ses performances puisqu'il sait "où chercher" :

Paramètres	Solution brute	Nouvelle solution sans cache	Nouvelle solution avec cache
N=10, x=20..60, s=400	300k t/s	125k t/s	800k t/s
N=10, x=200..600, s=4000	30k t/s	14k t/s	100k t/s
N=50, x=20..60, s=2000	26k t/s	1400 t/s	140k t/s
N=10, x=20..60, s=500	8000 t/s	100k t/s	700k t/s
N=10, x=20..60, s=550	27 t/s	100k t/s	700k t/s

Et pour les paramètres classiques, on constate qu'on est du même ordre de grandeur entre les solutions en terme de performance (un peu plus rapide avec cache, un peu moins sans cache).

L'algorithme autorise d'obtenir plusieurs fois la même valeur dans un tuple. Si on veut avoir des valeurs distinctes:
* soit on considère à chaque itération seulement les x qu'on n'a pas rencontré jusque là (mais la distribution deviendra légèrement biaisée)
* soit on ne s'en soucie pas et on rejette les solutions avec des valeurs identiques

Dernier point concernant cette solution, c'est son principal défaut : elle calcule des valeurs "astronomiques" à cause des factoriels. La formule fait intervenir des valeurs de l'ordre de (s*N)^N. C'est compliqué à stocker, mais je m'en suis sorti en calculant tout avec des valeurs encodées sous la forme exponentielle (mais qui peuvent quand même atteindre leurs limites). Ca implique des approximations, mais puisque toutes les valeurs comparées sont astronomiques, alors ça passe.

>>> Projet C++ pour les intéréssés/motivés : RandomGenerationWithSum.zip (nouvelle solution dans src/GenerationByFormula.cpp)

[Sve@r]

Bonjour

M'a intéressé ce problème. D'autant plus que je l'ai déjà eu (devant générer des jeux d'essais mais dont les valeurs dépendaient des valeurs précédentes). Pour le coup j'avais utilisé la solution de tbc92 (je génère sans me poser de question et si ça valide je garde). Toutefois mes contraintes étaient quand-même moins drastiques que tomber pile poil sur 400 avec une somme de 10 nombres (ce qui ressemble alors plus à l'algorithme du singe savant ou du tri stupide).

Mais l'idée de Flodelarab m'a plu et pour passer le temps j'ai décidé de la modéliser en Python.

Le code

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
#!/usr/bin/env python3
# coding: utf-8
 
from itertools import *
 
# La fonction qui vérifie la règle
def rule(tab): return sum(tab) == 400
 
# Génération de tous les n nombres qui valident la règle
def generate(tab, n):
	for x in combinations_with_replacement(tab, n):
		if rule(x): yield x
# generate()
 
# Go (on va générer au fil de l'eau sans stocker les résultats parce que des résultats il y en a une chiée)
cpt=0
for g in generate(range(20, 61), 10):
	cpt+=1
	print(cpt, g, sum(g))
# for

Et ce que ça a donné (je ne mets que la fin et pas les 97809616 résultats)

97809609 (39, 39, 39, 39, 40, 40, 41, 41, 41, 41) 400
97809610 (39, 39, 39, 40, 40, 40, 40, 40, 40, 43) 400
97809611 (39, 39, 39, 40, 40, 40, 40, 40, 41, 42) 400
97809612 (39, 39, 39, 40, 40, 40, 40, 41, 41, 41) 400
97809613 (39, 39, 40, 40, 40, 40, 40, 40, 40, 42) 400
97809614 (39, 39, 40, 40, 40, 40, 40, 40, 41, 41) 400
97809615 (39, 40, 40, 40, 40, 40, 40, 40, 40, 41) 400
97809616 (40, 40, 40, 40, 40, 40, 40, 40, 40, 40) 400

(résultats générés en 39 minutes)

[Flodelarab]

Du coup, je suis allé chercher dans mes tablettes. Script bash, bien sûr. Ou awk. Ça dépend du point de vue.

Avec répétition :

Code bash :

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
#!/bin/bash
 
#awk -vn=3 -vobj=120 -vmin=20 -vmax=60 '
awk -vn=10 -vobj=400 -vmin=20 -vmax=60 '
BEGIN {
	tab[1]=min-1;
	ind=1;
	while (fini!=1)
	{
		tab[ind]++;
		while (tab[ind]+max*(n-ind) + prec[ind] < obj)
			tab[ind]++;
		if ((tab[ind]>max)||(tab[ind]*(n+1-ind) + prec[ind] > obj))
		{
			delete tab[ind];
			ind--;
			if (ind==0)
				fini=1;
		}
		else
		{
			ind++
			tab[ind]=tab[ind-1]-1;
			prec[ind]=prec[ind-1]+tab[ind-1];
			if (ind==n)
			{
				s="";
				tab[ind]=obj-prec[ind];
				for (i=1;i<=n;i++)
					s=""s" "tab[i];
				print s;
			}
		}
	}
 
}' /dev/null

Sans répétition :

Code bash :

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
#!/bin/bash
 
#awk -vn=3 -vobj=120 -vmin=20 -vmax=60 '
awk -vn=10 -vobj=400 -vmin=20 -vmax=60 '
BEGIN {
	tab[1]=min-1;
	ind=1;
	while (fini!=1)
	{
		tab[ind]++;
		while (tab[ind]+max*(n-ind) -(n-ind-1)*(n-ind)/2 + prec[ind] < obj)
			tab[ind]++;
		if ((tab[ind]>max)||(tab[ind]*(n+1-ind) +(n-ind)*(n+1-ind)/2 + prec[ind] > obj))
		{
			delete tab[ind];
			ind--;
			if (ind==0)
				fini=1;
		}
		else
		{
			ind++
			tab[ind]=tab[ind-1];
			prec[ind]=prec[ind-1]+tab[ind-1];
			if (ind==n)
			{
				s="";
				tab[ind]=obj-prec[ind];
				for (i=1;i<=n;i++)
					s=""s" "tab[i];
				print s;
			}
		}
	}
 
}' /dev/null

[Sve@r]

Script bash, bien sûr. Ou awk. Ça dépend du point de vue.

J'admire tes connaissances awk (moi je l'utilise bêtement pour examiner mes scripts comme par exemple détecter des lignes vides qui se suivent, je ne l'aurais jamais imaginé pour faire une recherche mathématique ).
Pour rendre ton programme similaire au mien, j'ai rajouté un cpt=0 sous le BEGIN et cpt++ quand tu affiches "s". Plus, lors de l'affichage, évidemment j'affiche "cpt" mais j'affiche aussi la somme des nombres (je l'avais mis dans mon code Python pour checker que le total faisait bien 400 et j'avais pas envie de l'enlever et me retaper 40mn de test pour voir le temps que ça prend sans ça donc j'ai préféré te le rajouter à ton code)
Donc le résultat (sur la même machine pour avoir un test équivalent autant que possible) en 14mn. Il n'y a pas à dire, awk (proche du C) carbure plus vite que Python.. mais nécessite en retour un peu plus d'instructions pour lui expliquer son job. Comme quoi on n'a rien sans rien
Ne reste qu'à porter ce code en C et voir le temps que ça prend (j'ai tenté mais ai abandonné au delete tab[ind])...

Faudra que tu m'expliques à quoi sert "/dev/null" en fin d'instruction (normalement on met le fichier à traiter mais /dev/null n'est pas un fichier destiné à être lu). Moi je l'ai enlevé et ça a marché (sinon j'aurais tenté /dev/zero qui, lui, est bien un fichier input)

Sans répétition

L'énoncé du PO semble indiquer qu'il peut y avoir répétition...

[Flodelarab]

Faudra que tu m'expliques à quoi sert "/dev/null" en fin d'instruction (normalement on met le fichier à traiter mais /dev/null n'est pas un fichier destiné à être lu). Moi je l'ai enlevé et ça a marché (sinon j'aurais tenté /dev/zero qui, lui, est bien un fichier input)

Strictement à rien. C'est juste que tout ce code a été produit à l'arrache. J'aurais pu aussi mettre une here-string <<<"dthgrsth" et me passer du mot clé BEGIN. Comme Linux attend sur l'entrée standard si aucun fichier n'est fourni alors qu'il en faut un, ce qui provoque un vrai blocage improductif, je préfère donner un fichier au hasard et ne pas me casser la tête.