On peut vouloir choisir un élément au hasard dans un flux, c'est à dire où on ne connait pas la fin, ou aussi où on ne peut pas revenir en arrière.
Temps : O(n), espace : O(1)
Implémentation Perl :
rand($.) < 1 && ($line = $_) while <>;print $line;
Implémentation Python :
import sys, random for n, line in enumerate(sys.stdin): if not random.randrange(n + 1): choice = line print choice
Sur n
éléments, l'élément i
a une probabilité d'être choisi de :
1 i i+1 n-1 1 --- x --- x --- x ... x --- == --- i i+1 i+2 n n
On ne prend pas en compte les éléments précédents i
dans l'algorithme, donc ils n'influencent pas la probabilité de i
. Les numérateurs et dénominateurs s'annulent, et il ne reste plus que 1 / n
.
Tous les éléments ont la même chance d'être choisis.