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.

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
9  
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
    
    
I've implemented several simple weighted random algorithms. Let me know if you have questions. –  Leonid Ganeline Jan 25 at 20:27

5 Answers 5

up vote 32 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

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
    
Should be the accepted answer imo. I like this better than the "interval" and "repeated entry" approach. –  Vivin Paliath Jul 21 at 19:33

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

This is a simple Python implementation:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    for (i, element) in enumerate(container):
        if random() <= probs[i]:
            break

    return element

and

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

In genetic algorithms this select procedure is called Fitness proportionate selection or Roulette Wheel Selection since:

  • a proportion of the wheel is assigned to each of the possible selections based on their weight value. This can be achieved by dividing the weight of a selection by the total weight of all the selections, thereby normalizing them to 1.
  • then a random selection is made similar to how the roulette wheel is rotated.

Roulette wheel selection

Typical algorithms have O(N) or O(log N) complexity but you can also do O(1) (e.g. Roulette-wheel selection via stochastic acceptance).

share|improve this answer

This gist is doing exactly what you are asking for.

public static Random random = new Random(DateTime.Now.Millisecond);
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(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

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

        double randomDouble = random.NextDouble() * sumOfChances;

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

        return argCount-1;
    }

you can use it like that:

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

The above code will most probably (%98) return 0 which is index for 'apple' for the given array.

Also, this code tests the method provided above:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

It gives an output something like that:

Start...
Head count:52
Tails count:48
share|improve this answer
1  
Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler –  gnat Jul 3 at 7:45
    
You are right, I was focused on code so I forgot to tell how it works. I will add an explanation about how it works. –  Ramazan POLAT Jul 6 at 6:23

protected by gnat Jul 3 at 7:44

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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