Génération de matrices

**Endast** · 06/10/2016, 00h12

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

**picodev** · 06/10/2016, 00h22

Bonjour,

le plus simple est de construire la matrice ligne par ligne. Pour chaque ligne, tu commences par la remplir avec le nombre voulu de 1 et tu la complète avec des 0. Ensuite tu appliques à cette ligne un algo de mélange type fisher yates.

**Pascaltech** · 06/10/2016, 09h59

Bonjour,

En tirant au sort avec une fonction random, les valeurs en dessous d'une valeur a correspondant à 0, les autres à 1.

La valeur a fixant la bascule entre 0 et 1 doit suivre la valeur de la somme des valeurs précédemment sorties de la ligne.

**wiwaxia** · 07/10/2016, 13h10

Bonjour,

Bonne idée, effectivement:

Envoyé par Pascaltech

... En tirant au sort avec une fonction random, les valeurs en dessous d'une valeur a correspondant à 0, les autres à 1.

La valeur a fixant la bascule entre 0 et 1 doit suivre la valeur de la somme des valeurs précédemment sorties de la ligne.

... ainsi que celle du nombre de cases encore indéterminées, et du nombre (N₁) de termes non nuls.
Il faut alors veiller à prendre une fonction de probabilité appropriée, afin d'éviter une accumulation de termes identiques en début ou fin de ligne.
Dans une ligne comportant (N_c) colonnes, la probabilité de sortie du (1) au rang (j) [ 0 < j <= N_c ] devrait être de la forme:
P_{(j, s)} = (N₁ - s)/(N_c - j + 1), en notant (s) la somme des (j - 1) termes précédents.
Le seuil de bascule vérifie dans ce cas: 1 - a = P_{(j, s)} .

On peut aussi envisager une série de tirages aléatoires sur une ligne entière, initialisée à zéro, et conduisant à l'apparition de (N₁) termes égaux à l'unité. Les instructions suivantes réalisent alors une distribution uniforme:

Code :

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

1
2
3
4
5
6
7
8
9
 
FOR j:= 1 TO Nc DO Mat[i, j]:=0;
Nt:= 0;
REPEAT
  j:= Random(Nc); Inc(j);
  IF Mat[i, j]=0 THEN BEGIN
                        Mat[i, j]:= 1; Inc(Nt)
                      END
UNTIL Nt=N1;

**Endast** · 07/10/2016, 16h10

Bonjour,

Merci beaucoup pour vos réponses, je préfère la première solution, beaucoup plus facile à mettre en oeuvre, et comme ça constitue pas le coeur du programme...

J'ai donc construit les deux vecteurs, et j'essaie maintenant de les concaténer (le vecteur constitué de 0 et de 1), le problème étant qu'ils ne sont pas de même taille...

J'ai tout essayé niveau fonction de concaténation : le ; les vertcat etc...

Je ne comprends pas bien ce que tu veux dire par remplir le vecteur par les 0. Les vecteurs sont censés être "extensibles" en Matlab non ?
Par contre un paramètre est connu, c'est la longueur de la ligne.

**picodev** · 07/10/2016, 16h43

Je ne connais pas la syntaxe matlab mais l'idée est de, par exemple, pour une matrice 5 lignes 8 colonnes avec 3 1 par lignes de créer la matrice

Code :

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

1
2
3
4
5
6
 
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1
0 0 0 0 0 1 1 1

puis de mélanger chaque ligne en utilisant un algorithme qui te donnera chaque permutation avec une même probabilité.

**Pascaltech** · 07/10/2016, 16h45

Envoyé par wiwaxia

Bonjour,

... ainsi que celle du nombre de cases encore indéterminées,

N₁ : nombre de 1 tirés
N_tir : nombre de cases tirées
N_t : nombre de tirage total
a : N₁ / N_t objectif
a_m : N₁ / N_t est le a mesuré
b : N₁ / N_tir

Bonjour,

Je le vois différemment pour la première partie de ton message : les cases indéterminées ne sont pas encore tirées, selon l'énoncé, alors je ne peux pas les intégrer. Je considère qu'elles sont vides. b est à comparer à a.
Si tu les considères égales à 0, tu peux comparer aussi a_m à a.

Envoyé par wiwaxia

et du nombre (N₁) de termes non nuls.

Oui.

Envoyé par wiwaxia

On peut aussi envisager une série de tirages aléatoires sur une ligne entière, initialisée à zéro, et conduisant à l'apparition de (N₁) termes égaux à l'unité.

C'est plutôt dans ce sens que je vois la solution.

Endast n'a pas précisé si a est toujours de la même valeur ou variable selon une donnée extérieure et à chaque tirage de nouvelle matrice. C'est un autre sujet, mais cela influe sur le code de résolution du problème.

Il y a un point à intégrer, c'est la fin de la ligne : s'il y pas assez de 1, ou trop et si les dernières cases sont tirées au sort, leur valeur doit être corrigée selon le résultat du compte final, c'est à dire qu'il faudra procéder à un nouveau tirage au sort ou fixer leur valeur.

**wiwaxia** · 07/10/2016, 18h03

Envoyé par Pascaltech

... Il y a un point à intégrer, c'est la fin de la ligne : imagines un funambule sur un monocycle sur un câble ; lorsqu'il arrive à la fin du câble, il doit pédaler plus ou moins fort selon la pente de ce dernier, déterminée par sa tension et le poids de l'ensemble funambule/monocycle.

S'il y pas assez de 1, ou trop et si les dernières cases sont tirées au sort, leur valeur doit être corrigée selon le résultat du compte final, c'est à dire qu'il faudra procéder à un nouveau tirage au sort ou fixer leur valeur.

Il n'y a pas de difficulté, si l'on a bien vu que P_{(j, s)} représente la probabilité de sortie du '1' dans la j^me colonne, compte tenu des (j - 1) tirages qui l'ont précédé.

Soit par exemple les deux cas limites suivants:

a) Le '1' est systématiquement apparu dans les (N₁) premières cases: la somme de ces termes est alors: s = N₁ , et la probabilité d'apparition du '1' au rang suivant (j = N₁ + 1):
P_{(j, s)} = (N₁ - N₁)/(N_c - N₁) = 0 .
L'apparition du zéro devient alors certaine, de même que pour toutes les colonnes suivantes.
Il va de soi que le nombre total de colonnes (N_c) excède celui des termes non nuls (N₁), et que le dénominateur ne s'annule jamais (N_c > N₁), sinon la matrice ne présenterait que des éléments égaux à l'unité, et ne serait plus aléatoire.

b) Le zéro est systématiquement apparu dans les (N_c - N₁) premières cases: la somme (s) de ces termes est alors nulle, et la probabilité d'apparition du '1' au rang suivant (j = N_c - N₁ + 1):

P_{(j, s)} = (N₁ - 0)/(N_c - (N_c - N₁)) = (N₁ / N₁) = 1 .
La valeur (1) sort obligatoirement, de même qu'aux tirages suivants, de proche en proche et jusqu'au bout de la ligne; on a en effet pour les termes ultérieurs, de rang (j = N_c - N₁ + k): s = k - 1 , d'où:

P_{(j, s)} = (N₁ - k + 1)/(N_c + 1 - (N_c - N₁ + k)) = (N₁ - k + 1) / (1 + N₁ - k) = 1 (k vérifiant la condition: k <= N₁ ) .

# La seconde méthode proposée est une variante de celle indiquée par Picodev; elle me paraît plus simple.

**Pascaltech** · 07/10/2016, 19h40

Envoyé par wiwaxia

...
La valeur (1) sort obligatoirement, de même qu'aux tirages suivants, de proche en proche et jusqu'au bout de la ligne; on a en effet pour les termes ultérieurs, de rang (j = N_c - N₁ + k): s = k - 1 , d'où:

P_{(j, s)} = (N₁ - k + 1)/(N_c + 1 - (N_c - N₁ + k)) = (N₁ - k + 1) / (1 + N₁ - k) = 1 (k vérifiant la condition: k <= N₁ ) .

# La seconde méthode proposée est une variante de celle indiquée par Picodev; elle me paraît plus simple.

Que représente k ?

Oui, la méthode de fixation puis mélange des 0 et 1 de picodev garantie le nombre correct de 1 dans la ligne.

Une autre solution est de choisir un modèle d'arrangement prédéterminé dans une liste (stockée dans une variable) qui n'a pas besoin d'être exhaustive, étant donné que le nombre de solution peut être très grand. Tu tires au sort l'arrangement et non la liste de 0/1, un pseudo tirage au sort. L'important est que le client y croit !!

**wiwaxia** · 08/10/2016, 16h09

Il m'est venu une idée: pourquoi se cramponner au remplissage ligne par ligne, et ne pas envisager un ensemencement aléatoire de la matrice entière, comme Endast semble l'avoir tenté ?

Envoyé par Endast

... 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à réussi à générer les matrices, mais celles-ci sont irrégulières (nombre de 1 pas égal sur chaque ligne) ...

Il suffirait seulement d'introduire une variable supplémentaire, afin de mémoriser le nombre de '1' déjà contenus dans chaque ligne, et de ne pas dépasser la limite convenue.
Le coeur du programme pourrait comporter, après initialisation de tous les termes à zéro, des instructions du genre:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
   Ntir:= 0; Ns1:= 0; Randomize;
   REPEAT
     Inc(Ntir);       Nxy:= Random(Nte);          // Nte = Nli * Nco
     i:= Nxy DIV Nco; Inc(i);
     j:= Nxy MOD Nco; Inc(j);
     IF ((ListeN1[i]<N_1) AND (Mat[i, j]<1)) THEN BEGIN
                                                    Inc(Ns1); Inc(ListeN1[i]);
                                                    Mat[i, j]:= 1
                                                  END
   UNTIL Ns1=Ntot1                                // Ntot1 = Nli * N_1
 END.

Voici l'image obtenue en écran-texte, pour une matrice de dimensions 50x80 (N_1 = 10):

Nom : Mat_50x80_NI=10.jpg
Affichages : 423
Taille : 138,5 Ko

Le temps de calcul reste bref pour un tableau beaucoup plus grand (2000x2000, N_1 = 1500: t = 0.11 s).

**tbc92** · 08/10/2016, 16h49

Je n'ai pas compris le code que tu postes, mais je ne vois pas du tout comment ça pourrait améliorer le process classique :
Pour chaque ligne
Bâtir une ligne aléatoire avec n fois le chiffre 0 et p fois le chiffre 1

**Pascaltech** · 08/10/2016, 17h02

Sur l'image, la deuxième ligne et la troisième en partant du bas n'ont que 9 cases rouges. Est-ce le découpage de l'image ?

L'intérêt d'une telle matrice global peut être de piloter la différence entre les lignes : ...(à des emplacements différents sur la ligne)

**wiwaxia** · 08/10/2016, 17h51

Envoyé par Pascaltech

Sur l'image, la deuxième ligne et la troisième en partant du bas n'ont que 9 cases rouges. Est-ce le découpage de l'image ?

Non, j'avais oublié d'inclure la condition interdisant d'augmenter plusieurs fois les termes du tableau (Mat[i, j]<1). Cela se produit peu souvent lorsque N1<<Nc, et l'anomalie reste discrète ... J'avais inspecté quelques lignes,mais cela m'avait échappé.
Merci de ta vigilance.

J'ai modifié le code en conséquence, et remplacé l'image.

**picodev** · 08/10/2016, 18h03

Le tout n'est pas de générer une matrice en respectant certaines contraintes, mais, comme il s'agit d'une génération «aléatoire», il faudrait surtout que chacune des matrices ait la même probabilité d'être choisie. C'est là le point le plus délicat.
Construire une ligne revient juste à piocher une permutation du multiset {0^z,1^u} avec z le nombre de 0 et u le nombre de un.

Avec l'algo de fisher yates

L'algorithme pour générer la matrice est hyper simple et ne comporte aucune difficulté d'implémentation (hormis les détails des bornes pour le mélange).
On part avec une ligne comportant le nombre correct de 1 et de 0, on mélange, on insère la ligne dans la matrice, on recommence jusqu'à avoir le bon nombre de lignes. Comme on a l'assurance d'avoir des permutations équiprobables (même avec des éléments non deux à deux distincts) , il faut juste s'assurer que la matrice est elle aussi générée de manière équiprobable. C'est rapide : il y a m×cnp(u+z,u) matrices de m lignes et n colonnes, chaque ligne devant comporter z zéro et u un, remarquons que n=z+u.
Pour une matrice donnée chaque ligne est générée avec une probabilité égale à 1/cnp(u+z,u), il y a m lignes à générer, donc la probabilité d'obtenir une matrice particulière est de 1/(m×cnp(u+z,u)), ce qui est le résultat cherché.
Pour une matrice m×n on a là un algo en 𝛩(mn).

Avec une fonction qui génère la ligne «case par case»

Si on dispose d'une fonction zero_ou_un(z,u) qui renvoie 0 avec une probabilité de z/(u+z) et 1 avec une probabilité de u/(u+z) alors on peut facilement générer une ligne :

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
zero_ou_un( z, u )
début
  r ← random(0,u+z) // renvoie un entier aléatoire de [0;u+z[
  si r<z alors
    renvoyer 0
  sinon
    renvoyer 1
fin.
 
créer_ligne(z, u)
début
  n ← u+z-1
  ligne ← []
  pour i de 0 à n faire // je commence les indices à 0
    ligne[i] ← zero_ou_un(z,u)
    si ligne[i]=0 alors
      z ← z-1
    sinon
      u ← u-1
    fin si
  fin pour
  renvoyer ligne
fin.

En gros pour s'assurer de l'équiprobabilité il suffit de remarquer qu'une ligne quelconque est produite avec une probabilité de u(u-1)...1 . z(z-1)...1/ [ (u+z)(u+z-1)...1 ] = u!z!/(u+z)! = 1/cnp(u+z,u). Même démonstration que précédemment pour l'équiprobabilité du choix de la matrice.
Ici à nouveau on a un algo en 𝛩(mn).

Algo général

En gros les deux algos précédents reviennent plus ou moins à : on choisi un entier aléatoirement entre 0 et cnp(u+z,u) qui nous donne une ligne et on réitère ce procédé autant de fois qu'il le faut.
Et c'est là qu'un problème apparaît : nous ne disposons pas d'un nombre suffisant de nombre aléatoires (même pseudo aléatoires) pour pouvoir sélectionner une parmi toutes les permutations dans le cas général.
En gros avec un PRNG comme celui des libc (en général) on a au mieux des cycles de 2³². Donc à partir de m×cnp(n,u)>2³² c'est foutu, il y aura des matrices qui ne seront pas générées. Le pire des cas étant u=z.
Ensuite, tout est de savoir si on besoin de vraiment atteindre toutes les matrices ou non, à quel besoin d'«aléatoire» on a à faire face, etc …

**Pascaltech** · 09/10/2016, 21h01

Bonsoir,

J'ai utilisé une autre méthode pour obtenir une répartition de 10 "1" dans une grille de 80 colonnes et 400 lignes :

Je tire au sort la valeur de l'écart entre le "1" et la première colonne de la portion de la grille correspondante x, c'est-à-dire la grille/nombre de "1" souhaités. En OOobasic :

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
REM  *****  BASIC  *****
 
rem ----- matrice ----------
Public document as object
 
Public a as integer
Public x as double
Public tir(20) as double
 
rem Impression -------------------------------------------------------------
Public col as integer		' numéro de la colonne en cours pour impression
Public lig as integer		' numéro de la  ligne	en cours pour impression
rem ------------------------------------------------------------------------
 
Sub lancement
document = ThisComponent
Feuille = document.Sheets.getByIndex(0)
 
col = 1
lig = 1
 
colmax = 80
maxtir = 10
randomize
for lig = 1 to 400
x = colmax / maxtir
	for i = 1 to maxtir
		tir(i) = (x-1)*rnd
		if tir(i) = 0 then
			tir(i) = 1
		endif
		col = col + tir(i)
		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
	next
	col = 1
next
 
End sub

La répartition entre les colonnes est homogène, du fait du positionnement de chaque "1" dans chaque portion de grille : col = i*x.

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 ajouté deux conditions : si le tirage au sort donne 0, j'ajoute une colonne, si je tire le dernier "1" j'ajoute 1 colonne. La fonction rnd est déséquilibrée sous OOobasic.

**tbc92** · 10/10/2016, 00h08

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** · 10/10/2016, 09h42

Bonjour,

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

**wiwaxia** · 10/10/2016, 11h36

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 ?

Envoyé par Pascaltech

... 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

Envoyé par Pascaltech

...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

Envoyé par Pascaltech

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

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

Envoyé par Pascaltech

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

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

Envoyé par Pascaltech

... 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** · 10/10/2016, 13h37

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 :

Nom : matrice_8.jpg
Affichages : 175
Taille : 23,2 Ko

Nom : matrice_8.jpg
Affichages : 175
Taille : 23,2 Ko

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 :

Nom : graphique_tuto.jpg
Affichages : 294
Taille : 101,8 Ko

Nom : graphique_tuto.jpg
Affichages : 294
Taille : 101,8 Ko

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

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) :

Nom : matrice_10.jpg
Affichages : 162
Taille : 416,4 Ko

Nom : matrice_10.jpg
Affichages : 162
Taille : 416,4 Ko

**tbc92** · 10/10/2016, 13h53

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.

Génération de matrices

Algorithmes et structures de données

Vue hybride

Discussions similaires

Partager

Partager