Génération de matrices

Version imprimable

05/10/2016, 23h12
Endast

Génération de matrices

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
05/10/2016, 23h22
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.
06/10/2016, 08h59
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.
07/10/2016, 12h10
wiwaxia

Génération de matrices
Bonjour, :)

Bonne idée, effectivement:

Citation:

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:

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;
07/10/2016, 15h10
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... :D

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.
07/10/2016, 15h43
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:

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é.
07/10/2016, 15h45
Pascaltech

Citation:

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.

Citation:

Envoyé par wiwaxia

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

Oui.

Citation:

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.
07/10/2016, 17h03
wiwaxia

Génération de matrices

Citation:

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.
07/10/2016, 18h40
Pascaltech

Citation:

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

Citation:

Envoyé par Pascaltech

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

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 .

#

Citation:

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

08/10/2016, 08h36
Pascaltech

Bonjour,

CQFD.

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

Comment calcules-tu le nombre total d'arrangements différents ?
08/10/2016, 10h41
wiwaxia

Génération de matrices

Salut, :D

Citation:

Envoyé par Pascaltech

... 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_N₁), 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_N₁^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.

Citation:

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

# 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.
08/10/2016, 10h43
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)! )
08/10/2016, 11h05
Pascaltech

Merci pour les réponses wiwaxia et tbc92.

1 pièce(s) jointe(s)

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

Citation:

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:

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

Pièce jointe 222204

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

08/10/2016, 15h49
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
08/10/2016, 16h02
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)
08/10/2016, 16h51
wiwaxia

Citation:

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.

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:

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 …

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:

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.

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:

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

10/10/2016, 08h42
Pascaltech

Bonjour,

Non, pas de problème, juste des variantes. Merci pour la tienne.
10/10/2016, 10h36
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 ?

Citation:

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

Citation:

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

Citation:

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:

Citation:

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:

Citation:

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 ?

3 pièce(s) jointe(s)

Citation:

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 :

Pièce jointe 222325

Citation:

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 :

Pièce jointe 222306

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:

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.

Citation:

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

Pièce jointe 222311

10/10/2016, 12h53
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.
10/10/2016, 13h17
picodev

Citation:

Envoyé par 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.

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.

Citation:

Envoyé par tbc92

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.
10/10/2016, 13h23
Pascaltech

1 pièce(s) jointe(s)

Citation:

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.

Citation:

Envoyé par picodev

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:

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}

10/10/2016, 14h24
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

Citation:

Envoyé par Pascaltech

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

Citation:

Envoyé par Pascaltech

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

Citation:

Envoyé par Pascaltech

... 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.
10/10/2016, 14h41
Pascaltech

Citation:

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.
10/10/2016, 14h41
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 à

Citation:

Envoyé par Pascaltech

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:

...
10/10/2016, 14h46
tbc92

Citation:

Envoyé par Pascaltech

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.
10/10/2016, 15h06
wiwaxia

Citation:

Envoyé par 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.

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

Citation:

Envoyé par Pascaltech

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.
10/10/2016, 19h44
Pascaltech

Citation:

Envoyé par tbc92

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 !

Citation:

Envoyé par wiwaxia

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é.
10/10/2016, 20h23
tbc92

Citation:

Envoyé par Pascaltech

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 :

Citation:

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.

Fuseau horaire GMT +2. Il est actuellement 04h44.