In article <03fc01c2f5ba$a04cb8e0$0300a8c0 / austin.rr.com>,
Hal E. Fulton <hal9000 / hypermetrics.com> wrote:
>Here's a little question for you.
>
>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.
>
>I've started this a couple of times,
>but have become convinced I'm making
>it too hard, and someone can probably
>come up with a three-liner.
>
>Any ideas?
>

You're talking about some kind of proportional selection scheme (hey, you 
wouldn't happen to be working on Genetic Algorithms, would you?).  One way 
would be to do what's called roulette wheel selection.  You can visualize 
a roulette wheel where each number is sized proportionally to the weight.
The bigger the weight, the more likely the 'roulette wheel' is to land on 
that item.

It would look something like:

#Warning: untested code!
class RouletteWheel
  def initialize(itemList)
    @rouletteList = []
    runningTotal = 0    
    @items = itemList
    calc_sum
    @items.each_with_index{ |w,i|
      prob = calc_prob(w)
      runningTotal += prob
      @rouletteList[i] = runningTotal
    }
  end

  def spin
    rn = rand
    prev = 0.0
    @items.each_with_index { |w,i|
      @rouletteList.each_with_index { |p,j|
        if rn.between?(prev,p)
          return @items[j]
        end
        prev = p
      }
    }
    #otherwise return the last one:
    return @items[-1]
  end

  private
  def calc_sum
    @items.each { |w|
      @sum += w
    }
  end

  def calc_prob(value)
    value/@sum.to_f
  end

end
    
#use it:

rw = RouletteWheel([10,20,3,42,121,5])
item = rw.spin #most likely to get 121, least likely to get 3

Or alternatively, you could have spin return the index of the item in the 
array.

Now of course you'd probably modify it so that the itemList passed in 
isn't just a list of integers, but objects which contain an integer 
weighting....

Phil