Weighted random selection from array
algorithm, arrays, random
Solution
Compute the discrete cumulative density function (CDF) of your list -- or in simple terms the array of cumulative sums of the weights. Then generate a random number in the range between 0 and the sum of all weights (might be 1 in your case), do a binary search to find this random number in your discrete CDF array and get the value corresponding to this entry -- this is your weighted random number.
Problem
I would like to randomly select one element from an array, but each element has a known probability of selection. All chances together (within the array) sums to 1. What algorithm would you suggest as the fastest and most suitable for huge calculations? Example: ``` id => chance array[ 0 => 0.8 1 => 0.2 ] ``` for this pseudocode, the algorithm in question should on multiple calls statistically return four elements on id `0` for one element on id `1`.