0
$\begingroup$

I read a blog post about a simple algorithm to select a random item from a list, certain items in the list were weighted to increase the chance of it being selected.

  1. Add up all the weights.
  2. Pick a number at random between 1 and the sum of the weights.
  3. Iterate over the items, decrementing the random number by the weight of the current selection.
  4. Compare the result to zero, if less than or equal to break otherwise keep iterating.

I'm no math guy, so I am trying to rack my brain why this technique is better than simply creating a new list and adding additional items based on the original items weight. In the example, Type = Oranges, Weight = 1, Type = Apples, Weight = 2, the new list would contain 2 apples and 1 orange.

$\endgroup$
3
  • $\begingroup$ What if you wanted oranges to be $\pi$ times more likely than apples? $\endgroup$
    – Dan
    Commented Mar 25, 2015 at 13:43
  • $\begingroup$ I have a question though -- in Step $2$, shouldn't the number to be picked lie between $0$ and the sum of the weights instead? (I believe the "number" here does not mean integer) $\endgroup$
    – LaBird
    Commented Mar 25, 2015 at 14:04
  • $\begingroup$ @LaBird, in the algorithm which he found, you would be correct. In OPs attempt, he limits himself to integer weights $\endgroup$ Commented Mar 25, 2015 at 14:07

1 Answer 1

0
$\begingroup$

Dan's comment higlights one issue: what if the weights were irrational? Or, if you don't allow such scenarii (e.g., because irrational numbers "do not exist when implementing on actual computers"), what if one weight was a rational like $1/10^{8}$? You would need to add a lot of duplicates to your list to simulate these weights, and the overall blowup in the size of the list will harm you. (It will take a huge amount of memory, and picking an item will also take more time.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .