Home

# Algorithmic Advent: 01 – Weighted picks

Published on 1 Dec 2010. Tagged with php, algorithmicadvent.

This is the first entry of a small advent calendar series featuring PHP snippets. Hopefully one or two of them will be useful to anyone.

Today, we start with a function to pick a random entry from a weighted array.

``````/**
* Picks an element from a weighted array
*
* @param  array \$map "Element to weight factor" mappings (<mixed> => <int>)
* @return mixed|null Picked element or null if empty array
*/
function pick(array \$map)
{
\$sum  = array_sum(\$map);
\$rand = mt_rand(0, \$sum - 1);
\$k    = 0;
\$pick = null;

foreach (\$map as \$element => \$weight) {
\$k += \$weight;
if (\$rand < \$k) {
\$pick = \$element;
break;
}
}

return \$pick;
}``````

This example will return „c“ in 60 % of the time, „b“ in 30 % and „a“ in 10 %.

``````\$weights = array(
'a' => 10,
'b' => 30,
'c' => 60,
);

for (\$i = 0; \$i < 50; \$i++) {
echo pick(\$weights) . ", ";
}``````

This example simulates the rolling of two 6-sided dice (2d6).

``````\$twoDice = array(
'2' => 1,
'3' => 2,
'4' => 3,
'5' => 4,
'6' => 5,
'7' => 6,
'8' => 5,
'9' => 4,
'10' => 3,
'11' => 2,
'12' => 1
);

\$results = array();

for (\$i = 0; \$i < 100; \$i++) {
\$pick =  pick(\$twoDice);
\$results[\$pick] .= '*';
}

ksort(\$results);

foreach (\$results as \$pick => \$amount) {
echo \$pick . ': ' . \$amount . '<br />';
}``````