Cover by Leonard Richardson, Lucas Carlson

Safari, the world’s most comprehensive technology and business learning platform.

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required

O'Reilly logo

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) ...

Find the exact information you need to solve a problem on the fly, or go deeper to master the technologies and skills you need to succeed

Start Free Trial

No credit card required