selecting a random item from a set

[Alexander Schmolck]

Paul Rubin <http://phr.cx@NOSPAM.invalid> writes:
> Alexander Schmolck <a.schmolck at gmx.net> writes:
> >   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.

Nice algorithm, but maybe *only* if you don't know the size in advance (have
constant time len) -- as far as I can see it does more than twice the work of
my original solution.

'as