Select element from array with probability proportional to its value

The usual technique is to transform the array into an array of cumulative sums:

 [10 60 5 25]  --> [10 70 75 100]

Pick a random number in the range from zero up to the cumulative total (in the example: 0 <= x < 100). Then, use bisection on the cumulative array to locate the index into the original array:

Random variable x      Index in the Cumulative Array      Value in Original Array-----------------      -----------------------------      ---------------------- 0 <= x < 10                      0                            1010 <= x < 70                      1                            6070 <= x < 75                      2                             575 <= x < 100                     3                            25 

For example, if the random variable x is 4, bisecting the cumulative array gives a position index of 0 which corresponds to 10 in the original array.

And, if the random variable x is 72, bisecting the cumulative array gives a position index of 2 which corresponds to 5 in the original array.

For an inverse proportion, the technique is exactly the same except you perform an initial transformation of the array into its reciprocals and then build the cumulative sum array:

[10 60 5 25]  -->  [1/10  1/60  1/5  1/25]  -->  [1/10  7/60  19/60  107/300]

For Inverse proportionality:

1. sum the array
2. Pick a random number between 0 and (n-1)*sum -1
3. Accumulate sum-value starting from the beginning until you are >= to the random value.

This is for proportional

Note: All values must be positive for this to work.

1. sum the array
2. Pick a random number between 0 and the sum-1
3. Accumulate the values starting from the beginning of the array until you are >= to the random value.

Php code:

/** * Returns a random item from an array based on a weighted value. * @param array $array ['foo' => 70, 'bar' => 30] Foo has a 70 percent chance of being returned * @return int|string */public function randomize(array $array){    $sumOfWeights = array_sum($array);    $random = rand(1, $sumOfWeights);    foreach ($array as $name => $weight) {        $random -= $weight;        if ($random <= 0) {            return $name;        }    }}

Find the sum of all the element in array. Then generate a random number in this range. The final selection will be the element in the index returned by the above function.