selecting a random item from a set

[Paul Rubin]

Peter Otten <__peter__ at web.de> writes:
> >   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.

It will always select the first element, but then on some (random)
subsequent passes through the loop, it will replace the selection.
For example, suppose there are two elements.  On the first pass, e
gets set to the first element.  On the second pass, e gets set to the
second element if random() < 0.5, i.e. 50% of the time.  So after the
loop is done, e is either the first or the second element, with equal
probability.  With k>2 elements, it works the same way.