----- Original Message -----
From: "Hal E. Fulton" <hal9000 / hypermetrics.com>

Again, interesting. But I keep thinking about Phil's
comment about order.

Is there a consequence to the fact that you are
iterating through a list in order? Might the
results be "clustered" in some way?
----------------------------

Ordering makes no difference (except possibly in how the errors will show up
if the boundary cases are wrong, like the `<' vs `<=' bug referenced
earlier).  Those boundary cases are a pain...

Looking at Daniel's code again (and I *would* suggest trusting a
mathematician on problems like this :), but with a simpler set of weights to
help the boundary conditions be more clear (and rewriting things a bit):

  def wrand weightArray
    total = 0
    weightArray.each {|object,weight| total += weight}
    val = rand total
    weightArray.each do |object,weight|
      val -= weight
      return object if val < 0
    end
  end

  10.times {puts wrand([[:never,0],[:always,1]])}

  #> always
  #> always
  #> always
  #> always
  #> always
  #> always
  #> always
  #> always
  #> always
  #> always


Clearly, `<=' is incorrect; `total' would be 1, `val' would always be 0, and
`:never' would always be selected.

This seems like a pretty straight-forward algorithm to me; why would you
think ordering has anything to do with it?  Especially since Daniel's hash
(like most hashes :) is not ordered in any particular way.  The `each'es in
his code could be done in different orders... which is in fact a bug!  It
wouldn't happen very often, but it could happen.

The order of the object-weight pairs is irrelevant to the correctness of the
algorithm, but the two passes must use the same order.

Tabby's algorithm avoids the whole issue by making just one pass.  It uses
many rands, but rand is cheap.  Very nice!  It reminds me of the shuffling
algorithm they can't seem to get right at
http://c2.com/cgi/wiki?LinearShuffle (well, they did eventually get it
right).  Did you come up with that, Tabby, or did you learn it somewhere?
It's lovely.

Chris