Get a randomly weighted key in a Map/Dictionary/Associative Array

Here’s a very useful function to retrieve a randomly weighted key from an associative array in PHP.

Sometimes you need to fetch random elements from a collection but you need some elements to have a little more chance than others to be fetched (business rules or whatever…)

[php]
srand(time()); //dont call this inside the function or you’ll get same result always
function getRandomWeightedKey($weighted_elements, $default_key) {
$weighted_ranges = array();
$weight_offset = 0;

//if you know weights are not gonna change you could
//move this part of the code to another place and cache it
//for better performance. Specially if you have a lot of weighted elements
foreach ($weighted_elements as $key => $weight) {
$weighted_ranges[]=array(‘key’=>$key,
‘range’=>array(intval($weight_offset),intval($weight_offset+$weight)));
$weight_offset += $weight;
}

//get a random number between the 0 and the maximum
$r = rand(0,$weight_offset);

foreach ($weighted_ranges as $range) {
if ($r >= $range[‘range’][0] && $r < $range[‘range’][1]) {
return $range[‘key’];
}
}

//this shouldn’t happen but Mr. Justin Case.
return $default_key;
}

//how to use it. (weights don’t necessarily need to add to 100,
//but it helps me to visualize things basing weights on 100
$weights = array("a" => 25, "b" => 25, "c" => 50);

$randomKey = getRandomWeightedKey($weights, "c");
[/php]

It should be trivial porting this code to the language of your choice. Enjoy.