From: google@... (Tom Payne)
Date: 2003-03-29T19:05:30+09:00
Subject: Re: Weighted random selection -- how would you do this?

"Hal E. Fulton" <hal9000@hypermetrics.com> wrote in message news:<03fc01c2f5ba$a04cb8e0$0300a8c0@austin.rr.com>...
> Given: A set of items, each with
> an associated integer representing
> the relative likelihood that each
> item will be selected.
> 
> Write: A method that will select
> a random item.

It's not exactly what you want (but there are good reasons for it
being different), but here's the code I've been using for ages:

module WeightedRand

  def select
    p = rand
    each do |prob, value|
      return value if p < prob
      p -= prob
    end
    nil
  end

end

a = [[0.5, :heads], [0.5, :tails]].extend(WeightedRand)
5.times { puts(a.select) }

The list of items is an Array of [Probability, Value] pairs. This
means that you don't have to compute the sum (i.e. normalise the
probabilities) each time you select something (good if you need to do
lots of selects).

Here's some more code:

module WeightedRand

  # Normalise probabilities
  def normalize!
    sum = 0.0
    each do |prob, value|
      sum += prob
    end
    unless sum.zero?
      collect! do |prob, value|
        [prob / sum, value]
      end
    end
  end

  # Equal probabilities
  def uniform!
    p = 1.0 / size
    collect! do |prob, value|
      [p, value]
    end
  end

end

# Convert a 'events' hash as described by the original poster to an
Array prob/value pairs

def futon_hash_to_wr(hash)
  hash.collect do |value, freq|
    [freq, value]
  end.extend(WeightedRand).normalize!
end

Regards,

Tom