Picking Random Elements Based on Weight

Question

Say we have an array of name and weight

Something like

Jane 5 John 3 Dane 0 Doe 1

If weight is 0, the name Dane should show up 1/10th of a time than if the weight is 1

The rest are proportional.

So name Jane will show up 5 more times than Doe

Maximum weight is 10

I am thinking of an efficient algorithm to pick names based on their weight.

The way I currently do is to just translate the weight into a very big array.

So Dane will have an entry. Jane will have 50 entries. And then I pick randomly where each entries have equal chance.

I am using PhP.

I wonder if there is a more efficient way.

http://stackoverflow.com/questions/445235/generating-random-results-by-weight-in-php — , Jan 28 '16 at 07:10

score 0 · Answer 1 · answered Jan 28 '16 at 07:32

You can use the following steps: Firstly, sum the values of all weight.

Secondly, Generate random number in between 1 and the summation.

Now, we have a random number which is less than or equal of summation of all weight. But we need to have one of the weights. Besides, it should have higher chances to get the higher weight.

We can do this by subtracting all weights one by one from the the generated random number. If the resultant value is non-negative than it may have lower weight. If the resultant value is negative that it should be a higher weighted element.

That would be O(n). I want a constant solution. But there doesn't seem to be any way — user4951, Jan 28 '16 at 16:14

Picking Random Elements Based on Weight

1 Answers1