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.
# alternative arboricole
Posté par Krunch (courriel, site web personnel) . En réponse au journal Tirage aléatoire dans un tableau. Évalué à 4.
pertinent adj. Approprié : qui se rapporte exactement à ce dont il est question.