Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Aléatoire contraint aux poids


Sujet :

Algorithmes et structures de données

  1. #1
    Membre habitué
    Aléatoire contraint aux poids
    Bonjour, comment vous vous y prendriez ?
    Le but: Attribuer des poids à des strings dans un tableau (le poids est dans la string au mot m), et
    les tirer aléatoirement en fonction des poids. (je n'ose pas demander du pseudo code, qui serait pourtant le bienvenu).
    Je bueugue total, des explications seraient aussi les bienvenues.
    Merci aux savants.
    Savoir pour comprendre et vice versa.

  2. #2
    Membre confirmé
    C'est vague… il y a mille manières d'attribuer des poids à des chaines de caractères, et mille manières de faire ensuite un tirage aléatoire.
    Peux-tu préciser un peu le contexte, et / ou ce que tu entends par « le poids est dans la string au mot m » et « les tirer aléatoirement en fonction des poids » ?

  3. #3
    Membre habitué
    Citation Envoyé par balkany Voir le message
    C'est vague… il y a mille manières d'attribuer des poids à des chaines de caractères, et mille manières de faire ensuite un tirage aléatoire.
    Peux-tu préciser un peu le contexte, et / ou ce que tu entends par « le poids est dans la string au mot m » et « les tirer aléatoirement en fonction des poids » ?
    Cite: « le poids est dans la string au mot m ?
    Le poids c'est un "x" entre 1 et 10 contenu dans la string. (pas de soucis pour l'extraction).
    Cite: « les tirer aléatoirement en fonction des poids ?
    Que ceux de moins que 5 sortent "k*x" fois moins souvent et ceux de plus que 5, "k*x" fois plus.
    Comment maîtriser l'insaisissable aléatoire ?
    Mais est-ce encore de l'aléatoire...
    Savoir pour comprendre et vice versa.

  4. #4
    Membre habitué
    Citation Envoyé par valentin03 Voir le message
    Cite: « le poids est dans la string au mot m ?
    Le poids c'est un "x" entre 1 et 10 contenu dans la string. (pas de soucis pour l'extraction).
    Cite: « les tirer aléatoirement en fonction des poids ?
    Que ceux de moins que 5 sortent "k*x" fois moins souvent et ceux de plus que 5, "k*x" fois plus.
    Comment maîtriser l'insaisissable aléatoire ?
    Mais est-ce encore de l'aléatoire...
    En clair: Quel traitement faire subir au nombre qui sort du générateur aléatoire
    pour le soumettre sa fréquence à: x*k
    Savoir pour comprendre et vice versa.

  5. #5
    Expert éminent sénior
    Bonjour

    Les poids sont-ils des nombres entiers naturels ? Si oui, il suffit répéter le mot un nombre de fois égal au poids, et tirer de façon equiprobable un mot.

    Exemple:

    Maman 6
    va 2
    au 1
    marché 5
    Cette liste devient :

    Maman
    Maman
    Maman
    Maman
    Maman
    Maman
    va
    va
    au
    marché
    marché
    marché
    marché
    marché
    
    On tire un nombre entre 1 et 14 : 11
    Le mot à la onzième place est "marché".

    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
    $ cat <<eof >fichier.txt
    > Maman 6
    > va 2
    > au 1
    > marché 5
    > eof
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt
    Maman
    Maman
    Maman
    Maman
    Maman
    Maman
    va
    va
    au
    marché
    marché
    marché
    marché
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    Maman
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    au
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    va
    $ awk '{for (i=1;i<=$2;i++) print $1;}' fichier.txt | sort -R | head -1
    marché
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  6. #6
    Membre habitué
    Citation Envoyé par valentin03 Voir le message
    En clair: Quel traitement faire subir au nombre qui sort du générateur aléatoire
    pour soumettre sa fréquence à: x*coeff k
    J'ai bien une méthode bourrin:
    Compter les "ns" sorties
    Stocker "n" aléatoire sorti et son "ns"
    Et pour chaque sortie, aller voir depuis combien de temps il n'est pas sorti.
    Il y a peut-être mieux ...?

    Citation Envoyé par Flodelarab Voir le message
    Les poids sont-ils des nombres entiers naturels ? Si oui, il suffit répéter le mot un nombre de fois égal au poids, et tirer de façon equiprobable un mot.
    Houla, l'imparable de la simplicité a frappé.
    Quand y a pas d'algo, y a pas de problème d'algo.
    Mais quand même c'est plus joli avec un algo.
    Savoir pour comprendre et vice versa.

  7. #7
    Responsable Qt & Livres



    Une autre solution, inspirée des probabilités discrètes de manière très directe. On suppose que tous les poids se somment à un (dans le cas contraire, il suffit de normaliser : diviser chaque poids par la somme des poids). Ensuite, on détermine la CDF (fonction de répartition, en français). Finalement, on tire un nombre de manière aléatoire entre 0 et 1 (bornes incluses) et on inverse la CDF : à quel mot correspond cette valeur de la CDF ?

    De manière plus détaillée, sur un exemple (ça marche mieux ). On considère avoir trois mots : a (poids 4), b (poids 3,5) et c (poids 2).
    Normalisation des poids : la somme vaut 4 + 3,5 + 2 = 9,5. Donc on a : a 0,421, b 0,368, c 0,211. Ces trois poids se somment bien à 1. On a déterminé la densité de probabilité (même si ce mot est plutôt réservé aux distributions continues… Passons.)
    On détermine la CDF : entre 0 et 0,421, c'est a ; entre 0,421 et 0,421 + 0,368 = 0,789, c'est b ; entre 0,789 et 1, c'est c.

    Ensuite, on tire des nombres au hasard : 0,1 (on génère a : 0 <= 0,1 < 0,421) ; 0,5 (on génère b : 0,421 <= 0,5 < 0,789), 0,9 (on génère c : 0,789 <= 0,9 <= 1). Dans grosso modo tous les langages, tu as une fonction pour générer un tel nombre assez facilement.

    Sinon, les méthodes précédentes peuvent se généraliser aux cas où les poids ne sont pas entiers : il faut juste les multiplier par un même nombre jusqu'à ce que tous soient entiers. Dans mon exemple, il suffit de multiplier par 2 (a 8, b 7, c 4). Ça reste bourrin, 'faut pas se cacher .
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  8. #8
    Expert éminent sénior
    Tiens, puisqu'on en est à reformuler, voici une autre façon de le dire :

    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    total=somme(poids)
    score=nombre_aléatoire_entre(0,total)
    indice_mot=0
    TANT QUE score > 0
        score -= poids[indice_mot]
        indice_mot++
    FINTANTQUE
    afficher mot[indice_mot]


    (Dans ce genre de tirage aléatoire, 0 est toujours inclus et le total toujours exclu)
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  9. #9
    Membre habitué
    Citation Envoyé par dourouc05 Voir le message
    Une autre solution, inspirée des probabilités discrètes de manière très directe. On suppose que tous les poids se somment à un (dans le cas contraire, il suffit de normaliser : diviser chaque poids par la somme des poids). Ensuite, on détermine la CDF (fonction de répartition, en français). Finalement, on tire un nombre de manière aléatoire entre 0 et 1 (bornes incluses) et on inverse la CDF : à quel mot correspond cette valeur de la CDF ?
    ça c'est pas mal, c'est plus subtil que bourrin; je vais étudier ça, qui paraît plus rapide que ma méthode bourrin (#6), ou celle de Floredelarab
    Savoir pour comprendre et vice versa.

  10. #10
    Expert éminent sénior
    Mais c'est la mêêêêêême.
    Cette réponse vous apporte quelque chose ? Cliquez sur en bas à droite du message.

  11. #11
    Membre habitué
    Citation Envoyé par Flodelarab Voir le message
    Mais c'est la mêêêêêême.
    C'est concis mais c'est trop ésotérique pour moi, puisque dans ton: "score=nombre_aléatoire_entre(0,total)" je voyais un comptage des sorties de: "nombre_aléatoire".
    Syntaxe = Tour de Babel de la programmation.

    Merci dourouc05, même en cent ans je n'aurais pu trouver un truc pareil.
    Savoir pour comprendre et vice versa.

  12. #12
    Membre chevronné
    Maman va au marché
    Bonjour,

    J'ai repris l'idée de dourouc05 sans procéder à la normalisation des poids.
    Il suffit pour cela de disposer de la liste des sommes partielles commençant à zéro, et se terminant par la différence entre le total et le dernier coefficient.

    Le coeur du programme se réduit à peu d'instructions:
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
               n:= Random(Total); k:= N_Mot;
               WHILE (n<Ls[k]) DO Dec(k);

    Voici l'affichage obtenu:


    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
      PROGRAM XXXX;
    
     USES Crt, E_Texte;
    
     CONST N_Mot = 4; Nm1 = N_mot - 1;
    
     TYPE Tab_Str = ARRAY[0..N_Mot - 1] OF String[7];
          Tab_E   = ARRAY[0..N_Mot - 1] OF Word;
    
     CONST ListeM: Tab_Str = (' Maman', ' va', ' au', ' marché');
           ListeE: Tab_E   = (4, 3, 2, 1);
    
     VAR Total: Word; ListeS: Tab_E;
    
     PROCEDURE Enumeration(Ls: Tab_E);
       VAR j, k, x, y: Byte; n, Smax: Word; Touche: Char;
       BEGIN
         RandSeed:= 1666555999; y:= 7;
         REPEAT
           Touche:= ReadKey; Inc(y);
           FOR j:= 1 TO 6 DO
             BEGIN
               x:= 13 * j;        Dec(x,10); GotoXY(x, y);
               n:= Random(Total); k:= N_Mot;
               WHILE (n<Ls[k]) DO Dec(k);
               E(0010); Write(n:2);
               E(0012); Write(k:3);
               E(0015); Write(ListeM[k])
             END
         UNTIL (Touche=#27)
       END;
    
     PROCEDURE Init_S(VAR L_: Tab_E; VAR T_: Word);
      CONST C1 = 3; L1 = 4; o = 9;
       VAR k, s: Word;
       BEGIN
         E(1011); Wt(C1, L1 - 1, 'Valeurs des coefficients:       ');
         E(0012); FOR k:= 0 TO Nm1 DO Write(ListeE[k]:9);
         E(0011); Wt(C1, L1 + 1, 'Valeurs des sommes successives: ');
         E(0014); s:= 0; L_[0]:= s; Write(ListeS[0]:o);
         FOR k:= 1 TO Nm1 DO BEGIN
                               Inc(s, ListeE[k - 1]); L_[k]:= s;
                               Write(ListeS[k]:o)
                             END;
         Inc(s, ListeE[k]); T_:= s;
         E(0010);           Write(Total:o)
       END;
    
     BEGIN
       Init_S(ListeS, Total); Enumeration(ListeS)
     END.


    @Flodelarab Sans vouloir en contester le contenu, je trouve ton pseudo-code un peu raide pour le lecteur débutant
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    TANT QUE score > 0
        score -= poids[indice_mot]
        indice_mot++
    FINTANTQUE


    Le français, notre affaire à tous
    Grand Dictionnaire Terminologique

  13. #13
    Membre éclairé
    Dicho
    Bonjour,

    La réponse de Flodelarab est assez sympathique même si la concision la rend un peu plus difficile à lire.

    Si on recherche la performance, on peut :

    1. ajouter un champs sum qui cumule les poids (-1 pour le premier ) :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     i  libellé poids sum
     0  Maman     6    5
     1  va        2    7
     2  au        1    8
     3  marché    5   13


    2. Ensuite tirer une valeur n entre 0 et sum_max ici 13 (inclus).

    3. Faire une recherche dichotomique de n (par exemple) dans sum :
    Code :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    si n = 10.
    4/2 = 2 -> i  => "au"  sum = 8 < n = 10
    4/4  + i = 3 => "marché"  sum = 13 > n = 10 et sum -poids < n // That's all folks !


    On peut même faire l'économie du champ sum en le calculant dans poids si ce dernier n'est plus utilisé.

    Bien sûr pour 4 éléments, le jeu n'en vaut pas la chandelle mais pour des nombres plus conséquents...

    Salutations
    Ever tried. Ever failed. No matter. Try Again. Fail again. Fail better. (Samuel Beckett)