O'Reilly logo

Ruby Cookbook by Leonard Richardson, Lucas Carlson

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

5.11. Choosing Randomly from a Weighted List

Problem

You want to pick a random element from a collection, where each element in the collection has a different probability of being chosen.

Solution

Store the elements in a hash, mapped to their relative probabilities. The following code will work with a hash whose keys are mapped to relative integer probabilities:

	def choose_ 
weighted(weighted)
	  sum = weighted.inject(0) do |sum, item_and_weight|
	    sum += item_and_weight[1]
	  end
	  target = rand(sum)
	  weighted.each do |item, weight|
	    return item if target <= weight
	    target -= weight
	  end
	end

For instance, if all the keys in the hash map to 1, the keys will be chosen with equal probability. If all the keys map to 1, except for one which maps to 10, that key will be picked 10 times more often than any single other key. This algorithm lets you simulate those probability problems that begin like, "You have a box containing 51 black marbles and 17 white marbles…":

	marbles = { :black => 51, :white => 17 }
	3.times { puts choose_weighted(marbles) }
	# black
	# white
	# black

I'll use it to simulate a lottery in which the results have different probabilities of showing up:

 lottery_probabilities = { "You've wasted your money!" => 1000, "You've won back the cost of your ticket!" => 50, "You've won two shiny zorkmids!" => 20, "You've won five zorkmids!" => 10, "You've won ten zorkmids!" => 5, "You've won a hundred zorkmids!" => 1 } # Let's buy some lottery tickets. 5.times { puts choose_weighted(lottery_probabilities) ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required