[kw-pm] picking a random list element, the hard way

Robert P. J. Day rpjday at crashcourse.ca
Fri Feb 25 10:52:09 PST 2011


  for your entertainment value, here's an optional exercise i'm going
to give out in next week's perl class.  it's not so much a perl
question as it is an algorithmic analysis question that's actually
quite simple to code once you figure it out.

  JOB: pick a random element from a list, such that each element in
the list is equally likely to be selected.

  sounds trivial, yes?  except here's the extra condition.  you're
given the list elements only *one at a time*.  you're not allowed to
store them, and you have no idea how many are coming.  and yet, you
still need to pick a random element out of that list.

  thoughts?

rday


More information about the kw-pm mailing list