PHP Weighted Random Choice & Selection Remove / Replacement

October 20, 2010    php weight random choice php

For something I have been doing in a php project of late, I needed to weight an array of values and as I go round and select the values remove the value or -1 from the weight depending on how many of the value are left in the weight.

If you have any improvements or suggestions then id very much like to here them :-)


$starttime = microtime();
$startarray = explode(" ", $starttime);
$starttime = $startarray[1] + $startarray[0];

/**
 * weighted_random()
 * Pick a random item based on weights.
 *
 * @param array $values Array of elements to choose from
 * @param array $weights An array of weights. Weight must be a positive number.
 * @return mixed Selected element.
 */
	function weighted_random($values, $weights){
	    $count = count($values);
	    $i = 0;
	    $n = 0;
	    $num = mt_rand(0, array_sum($weights));
	    while($i < $count){
	        $n += $weights[$i];
	        if($n >= $num){
	            break;
	        }
	        $i++;
	    }
	    return $i;
	}

	function recalc($val,$values,$weight){

		//two steps to consider here, -1 from the weight and if the weight is <=0 unset both the value and the weight.
		if($weight[$val]-1<=0){
			unset($weight[$val]);
			unset($values[$val]);

			$new_values = array();
			$new_weight = array();

			foreach($values as $k=>$v){
				$new_values[]=$v;
				$new_weight[]=$weight[$k];
			}

			return array($new_values,$new_weight);

		}else{
			$weight[$val]=$weight[$val]-1;
			return array($values,$weight);
		}

	}


	//in the context of what im doing lets get this right.

	$values = array(0=>"164-2",1=>"164-1",2=>"2-2");
	$weights = array(0=>1,1=>2,2=>1);

	//now we wanna select 4 values but edit them as we go round.

	$find = 3;

	for($i=0;$i<$find;$i++){

		$val = weighted_random($values,$weights);
		echo $val.'  |  ';
		echo $values[$val].'
'; list($values,$weights) = recalc($val,$values,$weights); } echo 'The new weights are '; print_r($weights); echo '
'; $endtime = microtime(); $endarray = explode(" ", $endtime); $endtime = $endarray[1] + $endarray[0]; $totaltime = $endtime - $starttime; $totaltime = $totaltime; echo "This page loaded in $totaltime seconds."; ?>

blog comments powered by Disqus