Discussion :

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

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}

[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

...

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

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

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

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

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