note 119942 deleted from function.mt-rand by cmb
| From: | cmb@php.net | Date: | Sun, 10 Nov 2019 12:43:27 +0000 |
| Subject: | note 119942 deleted from function.mt-rand by cmb | ||
| References: | 1 | Groups: | php.notes |
| Request: | Send a blank email to php-notes+get-212995@lists.php.net to get a copy of this message | ||
Note Submitter: Vitaly
----
Generate random number by Array weights.
Implementation of Vose's Alias Method (http://www.keithschwarz.com/darts-dice-coins/)
<?php
function random_aliasMethod($weight, &$prob = array(), &$alias = array())
{
$count = count($weight);
if (empty($prob)) {
$small = array(); $large = array();
$sum = array_sum($weight);
foreach ($weight as $i => &$w)
($w *= $count / $sum) < 1 ? $small[] = $i : $large[] = $i;
unset($w);
while (!empty($small) AND !empty($large)) {
$l = array_pop($small);
$g = array_pop($large);
$prob[$l] = $weight[$l];
$alias[$l] = $g;
($weight[$g] += $weight[$l] - 1) < 1 ? $small[] = $g : $large[] = $g;
}
foreach ($large as $i)
$prob[$i] = 1;
foreach ($small as $i)
$prob[$i] = 1;
}
return mt_rand() / mt_getrandmax() <= $prob[$i = mt_rand(0, $count - 1)] ? $i : $alias[$i];
}
// Example:
$weight = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 100);
$result = random_aliasMethod($weight);
// Distribution test:
$prob = array(); $alias = array(); // for cache
$results = array_fill(0, count($weight), 0);
for($i = 0; $i < 10000; ++$i) {
$results[random_aliasMethod($weight, $prob, $alias)]++;
}
print_r($results);
/*
[0] => 0
[1] => 70
[2] => 136
[3] => 190
[4] => 250
[5] => 322
[6] => 401
[7] => 444
[8] => 492
[9] => 596
[10] => 627
[11] => 6472
*/