Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have, for example, this table

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

I need to return random fruit. But apple should be picked 4 times frequently then lemon and 2 times frequently then orange.

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

What is general algorithm to implement this behavior?

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

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

share|improve this question
8  
that should be the same formula for obtaining random loot in Diablo :-) –  Jalayn May 29 '12 at 9:12
1  
@Jalayn: Actually, the idea for the interval solution in my answer below comes from what I remember about combat tables in World of Warcraft. :-D –  Benjamin Kloster May 29 '12 at 10:30
    
See also –  BlueRaja - Danny Pflughoeft Sep 26 '12 at 0:04
    
add comment

4 Answers 4

up vote 26 down vote accepted

The 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:

  1. Prepare a list of intervals that cover 0 to sum(weights). Each interval represents one fruit, its length being the weight of this fruit, so for your example:

    intervals = [3, 5, 6]
    

    Where an index of 0-3 represents an apple, 4-5 an orange and 6 a lemon.

  2. Generate a random number n in the range of 0 to sum(weights)

  3. Find the interval in which n falls and you got your fruit.

This approach requires more processing power than the first, but less memory and supports floating point weights.

share|improve this answer
2  
the interval solution seems nice –  Jalayn May 29 '12 at 9:16
1  
This was my first thought :). But what if I have got table with 100 fruits and weight could be around 10k? It will be very large array and this will be not as efficient as I want. This is about first solution. Second solution looks good –  fl00r May 29 '12 at 9:25
1  
I've implement this algorithm in Ruby github.com/fl00r/pickup –  fl00r May 29 '12 at 14:26
add comment

Here's an algorithm (in C#) that can select random weighted element from any sequence, only iterating through it once:

    public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
    {
        int totalWeight = 0; // this stores sum of weights of all elements before current
        T selected = default(T); // currently selected element
        foreach (var data in enumerable)
        {
            int weight = weightFunc(data); // weight of current element
            int r = Random.Next(totalWeight + weight); // random value
            if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
                selected = data; // it is the probability of discarding last selected element and selecting current one instead
            totalWeight += weight; // increase weight sum
        }

        return selected; // when iterations end, selected is some element of sequence. 
    }

This is based on the following reasoning: let's select first element of our sequence as "current result"; then, on each iteration, either keep it or discard and choose new element as current. We can calculate the probability of any given element to be selected in the end as a product of all probabilities that it wouldn't be discarded in subsequent steps, times probability that it would be selected in the first place. If you do the math, you'd see that this product simplifies to (weight of element)/(sum of all weights), which is exactly what we need!

Since this method only iterates over the input sequence once, it works even with obscenely large sequences, provided that sum of weights fits into an int (or you can choose some bigger type for this counter)

share|improve this answer
    
I would benchmark this before assuming it's better just because it iterates once. Generating just as many random values isn't exactly fast either. –  Jean-Bernard Pellerin Jun 20 '13 at 22:59
1  
@Jean-Bernard Pellerin I did, and it is actually faster on large lists. Unless you use cryptographically strong random generator (-8 –  Nevermind Jun 21 '13 at 7:28
add comment

Already present answers are good and I'll expand on them a bit.

As Benjamin suggested cumulative sums are typically used in this kind of problem:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

To find an item in this structure, you can use something like Nevermind's piece of code. This piece of C# code that I usually use:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

Now to the interesting part. How efficient is this approach and what's most efficient solution? My piece of code requires O(n) memory and run in O(n) time. I don't think it can bi done with less then O(n) space but time complexity can be much lower, O(log n) in fact. Trick is to use binary search instead of regular for loop.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess > lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

There is also a story about updating weights. In the worst case updating weight for one element causes update of cumulative sums for all elements increasing the update complexity to O(n). That too can be cut down to O(log n) using binary indexed tree.

share|improve this answer
    
Good point about binary search –  fl00r May 29 '12 at 14:28
    
Nevermind's answer doesn't need extra space, so it's O(1), but adds runtime complexity by repeatedly generating random numbers and evaluating the weight function (which, depending on the underlying problem, could be costly). –  Benjamin Kloster May 29 '12 at 15:05
1  
What you claim to be "more readable version" of my code is actually not. Your code needs to know total sum of weights, and cumulative sums, in advance; mine doesn't. –  Nevermind May 29 '12 at 17:58
    
@Benjamin Kloster My code only calls weight function once per element - you can't do any better than that. You're right about random numbers, though. –  Nevermind May 29 '12 at 17:59
    
@Nevermind: You only call it once per call to the pick-function, so if the user calls it twice, the weight function is called again for each element. Of course you could cache it, but then you're not O(1) for space complexity anymore. –  Benjamin Kloster May 29 '12 at 19:29
show 7 more comments

This gist is doing exactly what you are asking for.

public int chooseWithChance(params int[] args)
{
    /*
     * This method takes number of chances and randomly chooses
     * one of them considering their chance to be choosen.    
     * e.g. 
     *   chooseWithChance(1,99) will most probably (%99) return 1 since 99 is the second parameter.
     *   chooseWithChance(99,1) will most probably (%99) return 0 since 99 is the first parameter.     
     */
    int argCount = args.Length;
    int sumOfChances = 0;

    for (int i = 0; i < argCount; i++) {
        sumOfChances += args[i];
    }

    int random = new Random(DateTime.Now.Millisecond).Next(sumOfChances);

    while ((random -=args[argCount-1])> 0)
    {
        argCount--;
        sumOfChances -= args[argCount -1];
    }

    return argCount-1;
}

you can use it like that:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(4,2,1);
Console.WriteLine(fruits[choosenOne]);

if you give weight as (1,1,98) it will most probably (%98) return 2 which is index for 'lemon' for your array.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.