Discussion :

[tbc92]

J'ai du mal à suivre ... il y a un problème non résolu avec ces grilles ?
Dans ce cas, voici une variante pour la solution, très différente des solutions proposées jusque là.

On veut construire une grille avec NL lignes et NC colonnes. Dans chaque ligne, il doit y avoir N1 fois le chiffre 1, et (NC-N1) fois le chiffre 0.

Voici un bout de pseudo-code :

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
 
XXX est une structure
   nbre est un booleen
   rrr est un reel
fin
 
Tb est un tableau de NC XXX  //    ( un tableau dans lequel j'ai NC fois ma structure XXX)
Pour i = 1 a N1
  TB[i].NBRE = 1
fin
Pour i = N1+1 a NC
  TB[i].NBRE = 0
fin
// Dans TB , j'ai N1 éléments avec le chiffre 1, et NC-N1 éléments avec le chiffre 0
 
Pour Lig = 1 a NL  // Pour chaque ligne qu'on veut générer
  Pour i = 1 a NC
    TB[i].rrr = random()
  fin
  Tri ( TB, rrr )  // Je trie mon tableau sur la colonne rrr, qui contient un nombre aléatoire, ainsi mes N1 chiffres 1 et mes chiffres 0 sont répartis aléatoirement sur la ligne
  // Ecriture des 0 et des 1 dans l'ordre de TB
  Pour i = 1 a NC
    Print ( tb[i].NBRE )
  Fin
  //Passage à la ligne suivante
Fin

[Pascaltech]

Bonjour,

Non, pas de problème, juste des variantes. Merci pour la tienne.

[wiwaxia]

Bonjour,

Je ne connais pas ce langage, mais peut-être se passe-t-il la chose suivante: dans les rares cas où 79 cases ont été remplies, et parmi lesquelles le '1' n'est présent que dans 9 d'entre elles, la probabilité de sortie de ce dernier devrait passer à l'unité: est-ce bien le cas ?

... Malgré plusieurs essais, j'obtiens un résultat de 3997 "1" pour 4000, c'est-à-dire qu'il y a 3 lignes avec 9 "1", ce que je n'explique pas ...

J'ai essayé de déchiffrer ton programme, mais il y a des choses que je ne comprends pas:
(a, col, lig) sont des entiers, et (x, tir(20) (?) ) des réels d'après les déclarations

...Public a as integer
Public col as integer
Public lig as integer

Public x as double
Public tir(20) as double ...

ce que confirment les instructions qui suivent

... x = colmax / maxtir
for i = 1 to maxtir
tir(i) = (x-1)*rnd ...

C'est après que je ne suis plus:

... if tir(i) = 0 then
tir(i) = 1
endif
col = col + tir(i) ...

le plus déroutant étant l'augmentation du nombre de colonnes:

... if i = maxtir then
col = col + 1
endif
Feuille.getCellByPosition(col,lig).value = 1
Feuille.getCellByPosition(col+85,lig).value = tir(i)
col = i*x ...

Combien de colonnes trouve-t-on dans les lignes du tableau constitué ? N'y aurait-t-il pas des '1' logés au-delà de la 80^me case ?

[Pascaltech]

Je ne connais pas ce langage, mais peut-être se passe-t-il la chose suivante: dans les rares cas où 79 cases ont été remplies, et parmi lesquelles le '1' n'est présent que dans 9 d'entre elles, la probabilité de sortie de ce dernier devrait passer à l'unité: est-ce bien le cas ?

En fait, je ne tire pas les 80 colonnes, je ne tire que la valeur de l'écart par rapport à la première colonne de la portion de la grille correspondante. Pour 10 "1" et 80 colonnes, cela fait des portions de 8 colonnes :

J'ai essayé de déchiffrer ton programme, mais il y a des choses que je ne comprends pas:
(a, col, lig) sont des entiers, et (x, tir(20) (?) ) des réels d'après les déclarations

J'ai essayé avec des entiers et cela me donne plus de lignes à 9 "1"; l'arrondi de la fonction rnd s'effectuant dans la variable : tir(i) = (x-1)*rnd lorsque celle-ci est déclarée entière.

Les deux confitions if sont pour palier la dissymétrie de la fonction rnd dans OOoBasic. Voici une gamme de tirage de séries de 500, la ligne violette superpose les autres lignes :



Et j'ai constaté que cette fonction est cyclique, elle sort toujours le même cycle suivant(pour une valeur entre 1 et 8), passé les 100 premières lignes :

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
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
	2						
		2						
		2						
		2						
								8
	1							
							7	
	1							
				4				
					5			
				4				
				4				
			3					
							7	
				4				
					5			
						6		
					5			
								8
		2						
		2						
				4				
	1							
						6		
			3					
								8
			3					
					5			
						6		
				4				
							7	
				4				
		2						
								8
				4				
	1							
				4				
		2						
						6		
						6		
		2						
				4				
						6		
								8
								8
					5			
							7	
0								
		2						
				4				
				4				
								8
								8
			3					
						6		
	1							
							7	
						6		
			3					
0								
	1							
								8
					5			
0								
				4				
		2						
					5			
					5			
			3					
					5			
0								
							7	
				4				
				4				
	1							
	1							
	1							
							7	
						6		
								8
0								
				4				
						6		
							7	
						6		
		2						
				4				
	1							
			3					
							7	
					5			
						6		
	1							
						6		
		2						
						6		
0								
				4				
						6		
						6		
					5			
							7	
			3					
						6		
		2						
				4				
		2						
			3					
								8
	1							
							7	
	1							
					5			
							7	
							7	
		2						
								8
			3					
					5			
			3					
		2						
					5			
					5			
	1							
0								
		2						
			3					
				4				
		2						
			3					
			3					
								8
					5			
							7	
						6		
							7	
							7	
	1							
							7	
					5			
				4				
							7	
0								
	1							
	1							
				4				
					5			
			3					
			3					
0								
					5			
							7	
				4				
	1							
					5			
				4

Alors pour palier ce déséquilibre, j'ajoute 1 colonne lorsque le tirage tombe sur 0 et j'ajoute aussi une colonne lorsque je tire la valeur maxi maxtir. Ces deux conditions seraient inutiles au tirage des 80 colonnes avec une fonction rnd d'un autre logiciel, je pense.

Combien de colonnes trouve-t-on dans les lignes du tableau constitué ? N'y aurait-t-il pas des '1' logés au-delà de la 80me case ?

C'est ce qui m'arrivait avec d'autres codages. Avec celui-ci, je reste dans les 80 colonnes, et 85 colonnes plus loin, j'affiche la valeur de l'écart tiré. Une vue du résultat, avec le nombre de tirs par colonne dans la partie basse(je suis désolé l'image est un peu grande et peu lisible lorsqu'elle est en 640) :

[tbc92]

Je cite : "Avec 10 chiffres 1 à répartir dans 80 colonnes, ça fait des portions de 8 colonnes"

Je ne suis pas complètement d'accord avec cela.

Dans le processus 'bourrin', on lance 80 fois la fonction random, et on lui demande un nombe entre 0 et 1, et selon ce nombre et selon un seuil calculé intelligemment, on détemrine si on met un 0 ou un 1 dans la cellule. On a donc 80 fois la fonction random() pour bâtir une ligne.
Et si je comprend bien ton idée, tu veux lancer cette fonction random() seulement 10 fois, pour chercher à positionner le "prochain" 1.
Et une fois le Premier 1 positionné, on refait un random() pour placer le 2ème 1 dans le reste de la ligne.
Le problème c'est que la 'Fonction de distribution' du 1er 1 n'est pas une fonction uniforme. ( Le premier 1 n'a pas la même probabilité d'apparaître en colonne 3 qu'en colonne 4...)
Et avec cette méthode, tu ne pourras pas reproduire strictement la fonction de répartition réelle. (En tout cas, pas de façon simple)

Eventuellement pour t'en convaincre, plutôt que positionner 10 "1" parmi 80 colonnes, positionne 35 "1" parmi 80 colonnes... ou mieux, positionne 75 "1" parmi 80 colonnes.

Ici, il semblerait qu'en plus la fonction Rnd() de ton langage ait un cycle trop réduit.
Souvent, les fonction Rnd() peuvent être initialisées avec un initRandom( integer) ; Tu peux probablement faire un InitRandom( heuresys ) régulièrement, pour remettre un peu plus d'aléatoire dans ton outil.

[picodev]

Je cite : "Avec 10 chiffres 1 à répartir dans 80 colonnes, ça fait des portions de 8 colonnes"

Je ne suis pas complètement d'accord avec cela.

Dans le processus 'bourrin', on lance 80 fois la fonction random, et on lui demande un nombe entre 0 et 1, et selon ce nombre et selon un seuil calculé intelligemment, on détemrine si on met un 0 ou un 1 dans la cellule. On a donc 80 fois la fonction random() pour bâtir une ligne.
Et si je comprend bien ton idée, tu veux lancer cette fonction random() seulement 10 fois, pour chercher à positionner le "prochain" 1.
Et une fois le Premier 1 positionné, on refait un random() pour placer le 2ème 1 dans le reste de la ligne.
Le problème c'est que la 'Fonction de distribution' du 1er 1 n'est pas une fonction uniforme. ( Le premier 1 n'a pas la même probabilité d'apparaître en colonne 3 qu'en colonne 4...)
Et avec cette méthode, tu ne pourras pas reproduire strictement la fonction de répartition réelle. (En tout cas, pas de façon simple)

Eventuellement pour t'en convaincre, plutôt que positionner 10 "1" parmi 80 colonnes, positionne 35 "1" parmi 80 colonnes... ou mieux, positionne 75 "1" parmi 80 colonnes.

Si, choisir le premier indice dans le tableau donnera la même probabilité de placer le 1 quelle que soit la colonne. Il faut «juste» bien manipuler la fonction random.
Effectivement si on répète cette méthode on peut tomber sur une colonne déjà remplie avec un 1, il faut donc recommencer avec un nouveau choix. Cela nécessitera beaucoup de choix quand la ligne est presque saturée car on choisira une cellule contenant un 1 avec un plus grande probabilité à chaque fois.
On peut contourner ce problème assez facilement, par exemple placer 75 un dans une ligne remplie de 80 zéro revient à à placer 5 zéro dans une ligne remplie de 80 un … Comme je le précisais dans un post précédent le pire des cas est de mettre n/2 1 dans une ligne de taille n.

Ce genre de problèmes est généralement résolu en appliquant (à nouveau) un algo de type fisher-yates. Pour placer u 1 dans une ligne de taille n, on crée un tableau d'entiers de de 0 `a n-1 (si les indices commencent à 0), on mélange ce tableau avec un fisher-yates et on prend les u premiers éléments comme les indicies où on placera les 1. C'est généralement plus efficaces que les piochages aléatoires itérés. On peut même s'arrêter après avoir mélangé seulement u éléments.

Ici, il semblerait qu'en plus la fonction Rnd() de ton langage ait un cycle trop réduit.
Souvent, les fonction Rnd() peuvent être initialisées avec un initRandom( integer) ; Tu peux probablement faire un InitRandom( heuresys ) régulièrement, pour remettre un peu plus d'aléatoire dans ton outil.

Tous les PRNG ont des cycles. À partir du moment où ce cycle est plus petit que m.n! avec une natrice de m lignes à n colonnes on ne pourra pas générer chaque solution.

[Pascaltech]

Et si je comprend bien ton idée, tu veux lancer cette fonction random() seulement 10 fois, pour chercher à positionner le "prochain" 1.

Oui. C'est vrai, je borde le tirage au sort, en imposant la présence d'un "1" dans chaque portion.




Le tirage est déséquilibré, je pense que cela est dû à l'arrondi du tirage de la fonction rnd. J'ai essayé maintes fois de l'optimiser, sans y arriver.

[Pascaltech]

Tous les PRNG ont des cycles. À partir du moment où ce cycle est plus petit que m.n! avec une natrice de m lignes à n colonnes on ne pourra pas générer chaque solution.

Ouais, alors un cycle de 156 valeurs différentes, c'est pour les gogos !!!!

Même en initialisant avec le commande randomize, quelque soit l'essai.

Voici le code en C de la fonction randomize et rnd de OOoBasic, si vous savez l'analyser :

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
Pour info, voici le code source en C des deux fonctions randomize et rnd de OpenOffice, issu du site opengrok*:
 
http://opengrok.adfinis-sygroup.org/source/xref/aoo-AOO34/main/basic/source/runtime/methods.cxx#3354
 
3339RTLFUNC(Randomize)
3340{
3341    (void)pBasic;
3342    (void)bWrite;
3343
3344    if ( rPar.Count() > 2 )
3345        OOoBasic::Error( SbERR_BAD_ARGUMENT );
3346    sal_Int16 nSeed;
3347    if( rPar.Count() == 2 )
3348        nSeed = (sal_Int16)rPar.Get(1)->GetInteger();
3349    else
3350        nSeed = (sal_Int16)rand();
3351    srand( nSeed );
3352}
3353
3354RTLFUNC(Rnd)
3355{
3356    (void)pBasic;
3357    (void)bWrite;
3358
3359    if ( rPar.Count() > 2 )
3360        OOoBasic::Error( SbERR_BAD_ARGUMENT );
3361    else
3362    {
3363        double nRand = (double)rand();
3364        nRand = ( nRand / (double)RAND_MAX );
3365        rPar.Get(0)->PutDouble( nRand );
3366    }
3367}

[wiwaxia]

Cette réponse longuement détaillée permet de mieux voir ce qui se passe.

Je regarderais de près les opérations internes du logiciel

... l'arrondi de la fonction rnd s'effectuant dans la variable : tir(i) = (x-1)*rnd lorsque celle-ci est déclarée entière ...

après que soit apparu le comportement franchement indigent du générateur de nombres pseudo-aléatoires

... Les deux conditions if sont pour palier la dissymétrie de la fonction rnd dans OOoBasic. Voici une gamme de tirage de séries de 500, la ligne violette superpose les autres lignes ... / ... j'ai constaté que cette fonction est cyclique, elle sort toujours le même cycle suivant (pour une valeur entre 1 et 8), passé les 100 premières lignes :

... Alors pour palier ce déséquilibre, j'ajoute 1 colonne lorsque le tirage tombe sur 0 et j'ajoute aussi une colonne lorsque je tire la valeur maxi maxtir. Ces deux conditions seraient inutiles au tirage des 80 colonnes avec une fonction rnd d'un autre logiciel, je pense ...

Ce qui s'impose, c'est soit de procéder à une initialisation appropriée (voir les indications de tbc92), soit de balancer le logiciel aux orties.

Il n'est pas rare, d'une manière générale, qu'un logiciel qui rend d'excellents services dans certains domaines (dessin, traitement de texte) se révèle tout à fait insuffisant dans un autre (calcul). Une solution simple serait de programmer un générateur congruentiel linéaire, dont l'exécution est compatible avec le types d'entiers gérés par OOobasic. Générateur de performances modestes peut-être (5 chiffres maximum), mais non débile comme celui qu'on t'a fourgué.

Je réagis de la même façon que tbc92 en ce qui concerne la méthode de répartition des '1'

... En fait, je ne tire pas les 80 colonnes, je ne tire que la valeur de l'écart par rapport à la première colonne de la portion de la grille correspondante. Pour 10 "1" et 80 colonnes, cela fait des portions de 8 colonnes ...

car tu semble confondre les notions de hasard et d'uniformité, comme chacun d'entre nous le fait spontanément. Je vois à l'instant que picodev vient de reprendre cette question. D'une manière exhaustive, comme à l'accoutumée.

[Pascaltech]

car tu semble confondre les notions de hasard et d'uniformité

Non, puisque j'affirme ne pas respecter le hazard, en bordant le tirage au sort.

[picodev]

Ma remarque ne concernait pas ton code en particulier. Je ne faisais que faire remarquer qu'il est illusoire avec les PRNG classiques de penser qu'on puisse générer n'importe quelle matrice avec une probabilité égale. Le simple fait que les PRNG possèdent des cycles (aussi long soient-ils) implique que non seulement on ne puisse choisir équitablement une matrice parmi toutes les matrices mais aussi que certaines matrices ne seront jamais générées. Cette remarque est également valable pour les autres algos à base de rand().
Par exemple avec un fisher-yates tu ne pourras jamais obtenir équiprobablement tous les mélanges d'un jeu de 52 cartes car log2(52!)>225.5 → il faudrait au moins un PRNG produisant des nombres pseudo-aléatoires avec un cycle > 2²²⁶. Pourtant on l'utilise souvent car «on s'en fout» ne pas arriver à produire tous les mélanges équiprobablement.

Edit: étant donné que les messages se sont vite accumulés, je répondais à

Ouais, alors un cycle de 156 valeurs différentes, c'est pour les gogos !!!!

Même en initialisant avec le commande randomize, quelque soit l'essai.

Voici le code en C de la fonction randomize et rnd de OOoBasic, si vous savez l'analyser :

Code :

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

...

[tbc92]

Oui. C'est vrai, je borde le tirage au sort, en imposant la présence d'un "1" dans chaque portion.

Tu t'interdis donc d'avoir par exemple les 10 "1" aux 10 premières colonnes, ou aux 10 colonnes du milieu, ou tous entre la 30ème et la 80ème colonne. C'est donc un autre besoin.

[wiwaxia]

car tu semble confondre les notions de hasard et d'uniformité

Non, puisque j'affirme ne pas respecter le hazard, en bordant le tirage au sort.

Tu impose pourtant une rigoureuse uniformité sur l'ensemble des huit tranches

Oui. C'est vrai, je borde le tirage au sort, en imposant la présence d'un "1" dans chaque portion.

ce qui exclut de fait toute séquence suffisamment serrée de plus de deux '1' , comme par exemple < 1 - 0 - 1 - 0 - 0 - 1 > , où 2 d'entre eux (au moins) appartiennent à la même tranche.

[Pascaltech]

Tu t'interdis donc d'avoir par exemple les 10 "1" aux 10 premières colonnes, ou aux 10 colonnes du milieu, ou tous entre la 30ème et la 80ème colonne. C'est donc un autre besoin.

Oui, c'est cela. Ce n'est pas une solution optimum, mais qui répond à la demande telle qu'elle est énoncée. Tu es trop perfectionniste, ça coûte cher la perfection !

Tu impose pourtant une rigoureuse uniformité sur l'ensemble des huit tranches ce qui exclut de fait toute séquence suffisamment serrée de plus de deux '1' , comme par exemple < 1 - 0 - 1 - 0 - 0 - 1 > , où 2 d'entre eux (au moins) appartiennent à la même tranche.

Oui, j'impose une rigoureuse uniformité, non je ne confond pas les notions de hazard et d'uniformité.

[tbc92]

Oui, c'est cela. Ce n'est pas une solution optimum, mais qui répond à la demande telle qu'elle est énoncée. Tu es trop perfectionniste, ça coûte cher la perfection !

La question initiale était :

Bonjour,

J'aimerais générer des matrices avec une particularité. Il faut qu'elles soient binaires (donc 0 ou 1) et que chacune des lignes soit composées du même nombre de 1 (à des emplacements différents sur la ligne).

J'ai déjà reussi à générer les matrices, mais celles-ci sont irrégulières (nombre de 1 pas égal sur chaque ligne). On m'a parle de combinaisons linéaires pour générer de telles matrices, mais je ne vois pas trop le rapport...

Auriez-vous une idée ?

Merci d'avance

A un moment, la demande a peut-être évolué vers le besoin que tu décris, mais j'ai zappé ce moment.