Journal Tirage aléatoire dans un tableau

Posté par  (site web personnel, Mastodon) .
Étiquettes : aucune
0
1
août
2006
Bonjour cher journal,

Aujourd'hui j'aimerais soumettre un problème à ta sagacité : celui du tirage aléatoire d'un élément dans un tableau.

Imaginons que je veuille tirer au hasard un élément dans un tableau qui en comporte N.

Je me souviens avoir lu quelque part qu'il suffit de faire :

1/N de prendre le premier sinon 2/N de prendre le second et ainsi de suite. Le dernier ayant une probabilité N/N d'être choisi si on arrive jusque là.

Cette solution à l'avantage d'être facile à implémenter cependant je n'arrive pas à démontrer que c'est vrai.

De plus, j'aimerais étendre ce principe à un dictionnaire qui comporte, pour chaque élément du tableau, une valeur qui est proportionnelle à la probabilité de prendre cet élément.

Exemple :

Considérons
{a : 1, b : 1, c : 2, d : 5, e :1}

La somme des valeurs des éléments vaut 10. d doit donc être choisi avec une probabilité 5/10, c avec une de 2/10, a,b et e avec une de 1/10.

Est-ce que l'implémentation suivant serait valable :


step = 0
sum = 10
for element in dictionnaire
{
step = step + element.value
nbr = random(0-10) % renvoie un nombre aléatoire entre 0 et 10
if nbr < step : choose element
else continue
}


Ainsi, dans notre exemple, il va choisir un nombre entre 0 et 10. Si ce nombre et 0, a va être choisi, step étant à 1.
Sinon, step devient 2 et un nouveau tirage est fait. Si le tirage est plus grand que 2, step devient direct 4. Un nouveau tirage est fait. si ça passe pas, step devient 9 et ainsi de suite.

Pensez-vous que cela soit correct ? Comment implémenteriez-vous un tel problème ?
Merci d'avance

  • # File dans ta chambre ...

    Posté par  (site web personnel) . Évalué à 10.

    ... et va faire tes devoirs !!!

    non mais ! ^_^

    • [^] # Re: File dans ta chambre ...

      Posté par  . Évalué à 2.

      Mouais bon, c'est vrai que dans les forums, ça aurait plus sa place, mais rien n'empêche de proposer une solution....

      Une idée si tu n'as pas trop de valeurs (en Python, mais je suis sûr que tout bon langage a ce qu'il faut):

      import random

      1 - tu génères une liste avec des occurences en nombre égal aux poids dont tu disposes dans ton dictionnaire (supposons d={'a' : 1, 'b' : 1, 'c' : 2, 'd' : 5, 'e' :1}):

      l = []
      for x, y in d.items(): l.extend([x]*y)

      2 - s'il s'agit de tirer au hasard un élément, il suffit de faire:

      print random.choice(l)

      3 - Si au contraire tu dois tirer tous les éléments:

      random.shuffle(l)
      for e in l: print e

      Valà, si ça peut aider...

  • # Bah

    Posté par  (site web personnel) . Évalué à 5.

    Et bien comme dans presque tous les langages tu as des primitives pour générer un nombre aléatoirement, moi je ne me prendrais pas la tête: je demanderais un nombre entre 0 et la longueur du tableau - 1...

  • # Random mal placé

    Posté par  . Évalué à 2.

    Ce que j'ai compris que tu veux faire :
    Faire un tirage au sort tel que chaque élément a une probabilité propre d'être choisi (probabilité égale à sa valeur dans le tableau / somme totale).

    Je pense que ton random est mal placé et devrait être fait une seule fois, avant la boucle, et que le reste est bon.

    • [^] # Re: Random mal placé

      Posté par  . Évalué à 0.

      Je ne comprends pas pourquoi mon message précédent est noté d'emblée à -2 !
      Et c'était pareil sur un autre message dans un forum.

      • [^] # Commentaire supprimé

        Posté par  . Évalué à -3.

        Ce commentaire a été supprimé par l’équipe de modération.

    • [^] # Re: Random mal placé

      Posté par  (site web personnel, Mastodon) . Évalué à 1.

      effectivement, quelque chose me chiffonait. En sortant le random de la boucle, cela me semble déjà plus cohérent !

      Mes livres CC By-SA : https://ploum.net/livres.html

  • # rand(0,count(tab) - 1)

    Posté par  . Évalué à 0.

    tout cela me semble bien compliqué pour sortir un element aléatoire d'un tableau ou alors j'ai manqué quelque chose ...

    est ce que (en php) :

    $tab = array('a','b','c','d','e','f','g','h','i');
    echo $tab[ rand(0,count($tab)-1) ];

    ne fait pas ce que tu veux ?

    Dam

    • [^] # Re: rand(0,count(tab) - 1)

      Posté par  . Évalué à 2.

      autant pour moi j'ai manqué la pondération pour chaque éléments.

      une solution pourrait être de multiplié dans le tableau le element par la valeur de pondération associée qui deviendrait :

      {a , b , c , c , d , d , d , d , d , e} et tu te retrouve avec le probleme qui trouve sa réponse dans mon post précédent non ?

      Dam

      • [^] # Re: rand(0,count(tab) - 1)

        Posté par  (site web personnel, Mastodon) . Évalué à 2.

        sauf que en pratique c'est pas forcément utilisable avec des valeurs très grande et comportant des décimales.

        C'est aussi relativement tout à fait inefficace en CPU et mémoire dans un problème ou ça doit être exécuté souvent (et récursivement)

        Mes livres CC By-SA : https://ploum.net/livres.html

  • # faux

    Posté par  . Évalué à 4.

    ta methode iterative est fausse. demonstration :

    la probabilite P(i) de choisir 1 parmi N elements equiprobables est 1/N :

    P(i)=1/N

    D'apres ta methode, P(i)=P(not(i-1))*(i/N)

    P(1)=1/N
    P(2)=P(not(1))*(2/N)=(1-1/N)*(2/N)=(2*N-2)/(N*N) != 1/N

    cqfd

    • [^] # Re: faux

      Posté par  (site web personnel, Mastodon) . Évalué à 4.

      tout à fait. C'est ce qui me gênait. Par contre, si tu sors le random de la boucle, cela fonctionne.

      Mes livres CC By-SA : https://ploum.net/livres.html

  • # En PHP

    Posté par  . Évalué à 1. 

    function randomProb($args)
{
    $start=0;
    for($i=0; $i<count($args); $i++) {
        if( !isset($args[$i]->name) || !isset($args[$i]->probability) ) {
            return false;
        }
        $args[$i]->start = $start;
        $start += $args[$i]->probability;
        $args[$i]->end = $start;
    }
    $result = mt_rand(1, 1000000*$start)/1000000;
    foreach($args as $once) {
        if($result >= $once->start && $result <= $once->end) {
            return $once->name;
        }
    }
    return false;
}
    $args est un tableau d'objet. L'attribut name est la valeur qui sera tirée et l'attribut probability est la probabilité qu'elle soit tirée au sort (plus c'est grand plus ça a de chance) Testé et approuvé (par contre, j'ai pas fait la démonstration)

    • [^] # Re: En PHP

      Posté par  . Évalué à 0.

      Sinon il y a shuffle(), tout simplement :)

  • # euh....

    Posté par  . Évalué à 2.

    Si j'ai bien compris ton algo, la proba de tirer le
    - 1er élément est a/10
    - 2e élément est (1-a/10) * (a+b)/10
    - 3e élément (1-(1-a/10) * (a+b)/10) * (a+b+c)/10
    - etc...

    il me semble que pour que ton algo soit correct, il faut tirer un seul nombre aléatoire au début et trouver l'élément pour lequel la somme cumulée est supérieur au nombre aléatoire...

    step = 0
    sum = 10
    nbr = random(0-10) % renvoie un nombre aléatoire entre 0 et 10
    for element in dictionnaire
    {
    step = step + element.value
    if nbr < step : choose element
    else continue
    }

    alors, la proba de tirer le
    - 1er élément est a/10
    - 2e élément est (a+b)/10 - a/10 = b/10
    - 3e élément (a+b+c)/10 - (a+b)/10 = c/10
    - etc...

    enfin si je ne me suis pas planté...

  • # Pas compris ton algo

    Posté par  . Évalué à 0.

    Attention, moi et les math, ça peut vraiment être mauvais certains jours, donc corrigez si c'est faut.

    Je ne suis surement pas bien attentif, mais j'ai pas bien compris ton algo. Personnellement, je vois une adaptation simple de l'algo dont tu te souviens. (1/N, 2/N, ...) J'espère que mon raisonement ne tombe pas sur ton algo.

    Il suffit de considérer que tu as un tableau de longueur (somme des tes proportionalités)

    Tu le remplit comme ceci :
    a, b, c, c, d, d, d, d, d, e
    Ensuite tu applique cet algo dessus.

    Donc dans la case 1, 1/10, dans la case 2, 2/10, ...


    Maintenant, si on formalise ceci, on passe de ton tableau original :
    {a : 1, b : 1, c : 2, d : 5, e :1}
    en un tableau de la forme (c'est du pseudo-LaTeX)
    {v_1 : p_1, v_2 : p_2, ... v_n : p_n }

    ce tableau se transforme en un autre tableau de taille S = \sum_i p_i :
    {v_1, v_1, ... v_2, v_2, ... v_n, v_n }
    avec comme probabilité de tirage de chaque élément seul pos_i / S (avec pos_i la position dans le tableau)

    Maintenant, arrangeons la formule.

    Pour le premier élément, la probabilité de le tirer est :
    P = sum_{i=1}^{p_1} i/S

    Pour l'élément n : (valable pour n = 1)
    P = sum_{i=1}^{p_n} (X+i)/S avec X=sum_{j=1}^(n-1) p_j (si n=1, X = 0)

    Ensuite, on applique les propriétés des séries "je ne sais plus le nom", on on obtient :

    P = (2X + p_n + 1) / 2S


    Mmmm je ne suis évidement pas sur, mais avec p_i = 1 pour tout i, on retombe sur ta formule dans le cas de probabilités égales (ouf). Je ne suis même pas sur que c'est cela que tu veux.

    • [^] # Re: Pas compris ton algo

      Posté par  . Évalué à -1.

      En supposant bien sur que l'algo dont tu te souviens est juste, ce qui semble contesté (à raison, il me semble, mais faudra que je retrouve le bon)

    • [^] # Re: Pas compris ton algo

      Posté par  . Évalué à 1.

      Marche pas si les pondérations sont décimale.
      Moi j'aurais un tableau contenant les nombre et leur coef, et avec un nombre aléatoire tiré entre 0 et la somme des coefs, je rechercherais le nombre en m'arretant dès que que j'ai une somme de coef égalant mon nombre aléatoire.

      S <- somme des coefficients.
      x <- random * S (random retournant un nb entre 0 et 1)
      i<- 0
      p<-pondération[i]
      Tant que(p!=x) {
      i++
      p<-p+pndération[i]
      }

      ecrire ( "le nombre tiré est")
      écrire ( nombre[i])

      Voilà approximattivement ce que je ferais.

      • [^] # Re: Pas compris ton algo

        Posté par  . Évalué à -1.

        Merde, c'est l'exemple du journal avec le random sorti de la boucle, comme l'ont dit plusieurs /o\
        Mais c'est à mon avis la bonne soluttion.

  • # Premier cas :

    Posté par  . Évalué à 1.

    J'ai pas compris exactement le principe, mais je ferai un truc du genre :

    si tu tombe sur un nombre entre 0/N et 1/N, tu choisis le premier, entre 1/N et 2/N, le second, etc.

    Après, suffit de faire un trux du genre trunc(alea()*N) pour trouver l'indice.

    [0..1/N[ * N -> [0..1[ -> trunc -> 0
    [(N-1)/N .. 1] * N -> [N-1 .. N[ -> trunc -> N-1

    si je me trompe pas.

  • # Forums

    Posté par  . Évalué à 2.

    Ce journal aurait eu sa place dans les forums...

  • # Faux, absurde et debordement

    Posté par  . Évalué à 4.

    Dans ton exemple :
    1ere passe
    -debut : step = 0
    -entre dans la boucle for
    step = 0+1 = 1
    nbr dans {0-10}
    element[0] choisit si nbr=0 (une chance sur onze, ca part mal)
    probablitié de choix de element[0]: 1/11

    2eme passe (si nbr<>0)
    - debut step=1
    - boucle : step=1+1=2
    nbr dans {0-10}
    element[1] choisit si nbr<2 (deux chances sur onze, on est pas beau)
    probabilité de choix de element[1] : 10/11*2/11=20/121 (le premier nbr n'est pas 0 et le second est 0 ou 1)

    3eme passe (si nbr<>0 puis nbr<>0 et nbr<>1)
    -debut step=2
    - boucle : step=2+2=4
    nbr dans {0-10}
    element[2] choisit si nbr<4 (4 chances sur 11)
    probabilité de choix de l'element[2] : 10/11*9/11*4/11= 360/1331 ( premier nbr différent de 0, deuxième nbr différent de 0 ou 1, troisième nbr est 0,1,2 ou 3)

    etc.

    Allez une solution qui marche en pseudo code :

    $total=0;
    pour $element dans $dico
    ($total=$total+$element.valeur;)
    fin pour;
    $index=aleatoire(1-$total); #nombre entier aléatoire entre 1 et $total inclus
    $i=1;
    $postition=0;
    tant que $i<$index
    ($i=$i+$dictionnaire[$position].valeur;
    $position=$position+1;)
    fin tant que;
    renvoit $position;

    Dans le cas particulier cité en exemple on aura bien un $total à 10
    donc $index sera compris entre 1 et 10
    si $index vaut 1 : pas d'execution de la boucle (1<1 est faux), le système renvoit $postion=0
    La position 0 a une chance sur 10 d'être choisie ($index=1)

    si $index vaut 2, un passage dans la boucle (1<2 est vrai), $i passe à 2 (1+$dictionnaire[0].valeur) et pas de deuxième passage dans la boucle. Le système renvoit $position=1
    La position 1 a une chance sur dix d'être choisie ($index=2)

    si index vaut 3 ou 4 : 2 passage dans la boucle :
    init : $i=1
    première passe : $i=2
    seconde passe : $i=4 et (4<4 est faux)
    Le système renvoit $position=2
    la position 3 a deux chances sur dix d'être choisie ($index=3 ou $index=4)

    etc.

  • # tu copieras 100 fois dans ta console

    Posté par  . Évalué à 6.

    Je ne ferais pas faire mes projets par mes petits camarades.

    Avec les consonnes en rouge et les voyelles en vert.

  • # alternative arboricole

    Posté par  (site web personnel) . Évalué à 4.

    Une alternative entre le tableau qui prend plein de place mais effectue un tirage en temps constant et l'itération compacte mais linéaire serait d'utiliser un arbre de probabilités qui prendrait un peu plus de place que le minimum mais qui serait parcouru en un temps logarithmique. 
    Par exemple (en Scheme parce que ça s'y prête bien et que ça fait longtemps, à noter que la fonction « random » de Guile renvoit un entier entre 0 compris et son argument non compris) :

    (define randelem-aux
  (lambda (n l c)
    (cond ((null? l) c)
          ((< (random n) 1) (randelem-aux (+ 1 n)
                                          (cdr l)
                                          (car l)))
          (else (randelem-aux (+ 1 n)
                                               (cdr l)
                                               c)))))

(define randelem
  (lambda (l)
    (randelem-aux 1 l '())))

(define randtree
  (lambda (tree)
    (if (not (list? tree)) tree
        (randtree (randelem tree)))))


    Il suffit ensuite d'appeller randtree avec en argument l'arbre de probabilité correspondant. Avec l'exemple cité, ça donnerait :
(randtree '(d (c c a b e)))

    Graphiquement, l'arbre ressemble à quelque chose comme ça :
     |___
 |      |
 d     |_____
        |  |  |  |   |
       c  c a b e


    L'idée c'est de descendre jusqu'à une feuille en prenant une branche au hasard à chaque fois. Au premier noeud, on a une chance sur deux de tomber sur « d » (donc 5/10). Au deuxième noeud, on a deux chances sur cinq (donc (1/2)*(2/5)=(2/10)) de tomber sur « c » et une chance sur cinq (donc (1/2)*(1/5)=(1/10)) pour « a », « b » et « e ».

    Bon faut aussi s'arranger pour construire l'arbre automatiquement et je laisse le soin aux matheux d'analyser l'efficacité de l'algorithme (en vitesse et en mémoire) en fonction de la répartition des probabilités.

    
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.

    

    

    

    


      

    • 

      
[^]
#
 
Re: alternative arboricole

      

      
Posté par  .
Évalué à -1.

      

      

      
NOOOOOOOOOoooooOOOOoooOOOOOoooooooOOOOoooOOOOoooOOOOOoooooOOoooOOOOoooooOOOoooooooOOOOOoooooooooooOOOOOoooOOOOON 
      
pas scheme !!!!
      
(ce commentaire est, peut-être, "optimisé" > 1280x1024)

      

      

      


      • 


    

    • 


  • 

    

#
 
tu avais du lire

    

    
Posté par  (site web personnel) .
Évalué à 5.

    

    

    
"Je me souviens avoir lu quelque part qu'il suffit de faire :
    

    
1/N de prendre le premier sinon 2/N de prendre le second et ainsi de suite. Le dernier ayant une probabilité N/N d'être choisi si on arrive jusque là."
    

    
En fait, tu avais du lire:
    

    
1/N de prendre le premier sinon 1/(N-1) de prendre le second et ainsi de suite. Le dernier ayant une probabilité 1/1 d'être choisi si on arrive jusque là."

    

    

    


      

    • 

      
[^]
#
 
Re: tu avais du lire

      

      
Posté par  (site web personnel, Mastodon) .
Évalué à 1.

      

      

      
Exact ! C'est à ça que je pensais. Maintenant est-ce que ma technique est valide une fois le nombre random sorti ?  J'ai bien l'impression...

      
Mes livres CC By-SA : https://ploum.net/livres.html

      

      

      

      


        

      • 

        
[^]
#
 
Re: tu avais du lire

        

        
Posté par  (site web personnel) .
Évalué à 2.

        

        

        
Bah oui, ça marche.
        

        
T'imagines un segment de longueur « somme des coefficients », fait de la concaténation de segments de longueur chaque coefficients. Tu tires un point au hasard, uniformément dans ce segment. Bon, doit y avoir plus formel comme démo, mais ...

        

        

        


          

        • 

          
[^]
#
 
Re: tu avais du lire

          

          
Posté par  (site web personnel) .
Évalué à 2.

          

          

          
Note X l'indice de l'élément tiré au hasard: en supposant l'indépendance de tes randoms, tu as :
          

          
P(X>k)=(1-1/N)(1-1/(N-1))(1-(1/N-2))...(1-1/(N-k+1))
          
           =(N-1)/N.(N-2)/(N-1).(N-3)/(N-2)....(N-k)/(N-k+1)
          
           =(N-k)/N
          

          
D'où
          

          
P(X=k)=P(X>k-1)-P(X>k)
          
           =(N-k+1)/N-(N-k)/N=1/N

          

          

          



          • 


        

        • 


      

      • 


    

    • 





Suivre le flux des commentaires




Note :
les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.