selecting a random item from a set

[Paul Rubin]

Alexander Schmolck <a.schmolck at gmx.net> writes:
> Quite a few algortihms prominently feature choosing/removing a
> single random element from a set at a time. On first sight I can't
> think of anything better to achieve this with `sets.Set` than
> something along the lines of:
> 
>   for dummy, randomElement in zip(range(randrange(len(s)+1)), s): pass
>   # possibly followed by
>   s.remove(randomElement)
> 
> Is there a better way? If not, how about something like Set.randompop()?

The classic way to do it goes something like this:

  for n, randomElement in enumerate(s):
     if random() < (1.0 / (n+1)):
        e = randomElement
   # 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 :).