w*****3
发帖数: 8 | 1 given an array, select an index based on their weights,
randomly, but proportional to the weights.
e.g.
(10,30) => (25%,75%)
(30,30,30,30) => (25%,25%,25%,25%) | k****u
发帖数: 133 | | X****r
发帖数: 3557 | 3 1. Calculate partial sum of the weights:
e.g. [10, 20, 30, 40] => [10, 30, 60, 100]
2. Generate a random number between 0 and the total weight,
(including 0 but not including the total weight),
For the above example, generate a random number in [0, 100),
let's say 56.
3. Search the array of partial sums to find the smallest
number than is greater than the random number. You can use
binary search. The index of this number is what you want.
For the above example, the number is 60, so weighted rand
【在 w*****3 的大作中提到】
: given an array, select an index based on their weights,
: randomly, but proportional to the weights.
: e.g.
: (10,30) => (25%,75%)
: (30,30,30,30) => (25%,25%,25%,25%)
|
|
