Marc Ermshaus

Linkblog

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 />';
}