selecting a random item from a set
Peter Otten
__peter__ at web.de
Tue Dec 30 18:50:39 EST 2003
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
More information about the Python-list
mailing list