selecting a random item from a set

[Peter Otten]

Paul Rubin wrote:

> 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.

You are right. I saw the typo and "overcorrected" by adding a break
statement in my mind.

> Note that you don't need to know the size of the set in advance.  You

That remark in your first post helped the misunderstanding. I managed to
overread the _in_ _advance_ and couldn't figure out a satisfactory break
condition - which now it turns out doesn't exist.

But now I've understood it.

Peter