[Tip] Choisir un élément aléatoire dans un flux

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.