selecting a random item from a set

[Peter Otten]

Paul Rubin wrote:

> The classic way to do it goes something like this:
> 
>   for n, randomElement in enumerate(s):
>      if random() < (1.0 / (n+1)):
>         e = randomElement

0 <= random() < 1
1.0/(n+1) == 1 for n == 0, so this will always choose the first element.

>    # possibly followed by
>    s.remove(randomElement)
> 
> Note that you don't need to know the size of the set in advance.  You
> can use the same method for (e.g.) choosing a random line from a file,
> without knowing how many lines the file has, and without having to
> read the file twice or store it in memory.
> 
> Seeing why this works (unless I made an error) is left as an exercise :).

Peter