Discussion :

[Endast]

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]

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]

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]

Bonjour,

Bonne idée, effectivement:

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

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]

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]

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.

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

Oui.

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]

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

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

... Que représente k ?

Dans le second cas limite envisagé (b), le rang relatif des termes non nuls confinés en fin de ligne, et comptés à partir du premier d'entre eux.

Exemple pour une matrice de 8 colonnes, comportant dans chaque ligne 3 termes égaux à l'unité:

Code :

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

1
2
3
4
5
 
rang de la colonne:  j =          1    2    3    4    5    6    7    8
m[i, j] =                         0    0    0    0    0    1    1    1
k =                               -    -    -    -    -    1    2    3
somme des termes précédents: s =  0    0    0    0    0    0    1    2

A partir de (j = 6) on a bien: s = k - 1 et: j = N_c - N₁ + k = 8 - 3 + k = 5 + k .

#

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

Les autres aussi ! Ce sont des solutions proposées pour le même énoncé.

[Pascaltech]

Bonjour,

CQFD.

Ce qui m'inquiète, c'est le tirage au sort.

Comment calcules-tu le nombre total d'arrangements différents ?

[wiwaxia]

Salut,

... Ce qui m'inquiète, c'est le tirage au sort.
Comment calcules-tu le nombre total d'arrangements différents ? Mon calcul est faux : Nc x 2!.

La valeur '1' doit être affectée à (N₁) éléments, dans une ligne qui en comporte (N_c), tous initialisés à zéro, ce qui donne:
A = N_c*(N_c-1)*(N_c-2)*...*(N_c-N₁+1) = (N_c)! / (N_c - N₁)! arrangements possibles;
cependant le résultat obtenu ne dépend pas de l'ordre d'affectation, de sorte que pour un ensemble de positions données (j₁, j₂, ... j_N1), les arrangements obtenus sont indiscernables, et il y en a (N₁)! .
Le nombre de combinaisons est par conséquent plus faible, et admet pour expression:
C_N1^N_c = A / (N₁)! = (N_c)! / ((N₁)! * (N_c - N₁)!) .
On trouve ainsi pour l'exemple déjà mentionné (N_c = 8 , N₁ = 3) : C₃⁸ = 8!/(3! * 5!) = 56 .

# L'énoncé, tel qu'il est donné, ne décrit que le remplissage individuel de chaque ligne, et n'impose rien en ce qui concerne leur succession, ce qui suggère un remplissage aléatoire.

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

# Les instructions que j'ai proposées - c'est du Pascal (on ne se refait pas), mais cela se lit comme du pseudo-code - conduisent à une répartition aléatoire uniforme de (N₁) termes non-nuls, comme le procédé de Fisher-Yates.

[tbc92]

Pour calculer le nombre de dispositions :
Prenons un exemple , 8 colonnes, et on veut disposer 5 fois le chiffre 0 , et 3 fois le chiffre 1 :
Considère que tu as 8 symboles différents A1 A2 A3 A4 A5 B1 B2 B3 ( à l'arrivée, les symboles Ai deviendront des 0, et les symboles Bj deviendront des 1)
On a 8 symboles possible pour la première colonne, puis pour chaque symbole choisi en 1ère colonne , on a 7 symboles possibles pour la 2ème colonne, etc, on a 8! dispositions.

Mais quand on va remplacer nos symboles par des 0 ou des 1, la disposition A1 A2 x x x x A3 ou la disposition A2 A1 x x x x A3 etc etc sont des doublons. Ces doublons sur les symboles Ai font qu'il faut diviser par 5!.
Et les doublons sur les symboles Bj font qu'il faut diviser par 3!

La formule générale : N est le Nombre de colonnes, P est le nombre de 0, N-P est le nombre de 1,
Le nombre de dispositions est N! / ( P! * (N-P)! )

[Pascaltech]

Merci pour les réponses wiwaxia et tbc92.

[wiwaxia]

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é ?

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



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

[tbc92]

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]

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]

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]

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]

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.