I have, for example, this table


+-----------------+
| fruit  | weight |
+-----------------+
| apple  |   4    |
| orange |   2    |
| lemon  |   1    |
+-----------------+


I need to return a random fruit. But apple should be picked 4 times as frequent as Lemon and 2 times as frequent as orange.

In more general case it should be f(weight) times frequently.

What is a good general algorithm to implement this behavior?

Or maybe there are some ready gems on Ruby? :)

PS
I've implemented current algorithm in Ruby https://github.com/fl00r/pickup

The conceptually simplest solution would be to create a list where each element occurs as many times as its weight, so
fruits = [apple, apple, apple, apple, orange, orange, lemon]

Then use whatever functions you have at your disposal to pick a random element from that list (e.g. generate a random index within the proper range). This is of course not very memory efficient and requires integer weights.

Another, slightly more complicated approach would look like this:

Calculate the cumulative sums of weights:
intervals = [4, 6, 7]



Where an index of below 4 represents an apple, 4 to below 6 an orange and 6 to below 7 a lemon.

Generate a random number n in the range of 0 to sum(weights).
Go through the list of cumulative sums from start to finish to find the first item whose cumulative sum is above n. The corresponding fruit is your result.

This approach requires more complicated code than the first, but less memory and computation and supports floating-point weights.
For either algorithm, the setup-step can be done once for an arbitrary number of random selections.
