Randomly select Items according to probability

Question

I have an array of elements. each element has a probability value attached to it. Lets say that I have an array of apples, red, yellow, green, blue, etc. like so.

- (Apple *)pickRandomApple
{
    Apple *red = [Apple redApple];
    Apple *green = [Apple greenApple];
    Apple *yellow = [Apple yellowApple];
    Apple *blue = [Apple blueApple];

    red.probability = 0.23f;
    green.probability = 0.85f;
    yellow.probability = 0.1f;
    blue.probability = 0.5f;
    NSArray *array = @[red,green,blue,yellow];

    return array[arc4random()%array.count];
}

I want to choose a random apple according the to probability property. How can I achieve this?

Thanks!

Answer 1

This is my method which is a bit more generic. Feel free to ask questions/ Edit

/**
 @param probabilitiesArray - array of integers who represent probabilities.
 If the first var in the array is 20 and the rest of the array's variables 
 sum up to 100 - there are 20% probability for first var to be chosen.
 */
-(int) randomNumberWithProbabilities:(NSArray *) probabilitiesArray
{
    //Sum up all the variables in the array
    int arraySum = 0;
    for(int i = 0;i < probabilitiesArray.count;i++)
    {
        arraySum += [probabilitiesArray[i] intValue];
    }

    //Random a number from 0 to the sum of the array variables
    int randomNumber = arc4random_uniform(arraySum);

    //Iterating through the array variable and detect the right slot for the random number
    int tempSum = 0;
    for(int i = 0;i < probabilitiesArray.count;i++)
    {
        tempSum += [probabilitiesArray[i] intValue];
        if(randomNumber < tempSum)
        {
            return i;
        }
    }
    return 0;
}

Answer 2

I understand from your question that you want to generate probabilities with strength, like Green are more probable to occur than red and so on... Well this question is not related to iOS or iPhone development, it is pure programming question and I don't think that there is one solution to it. Here is my solution and I would like to use simple solutions usually.

Before posting the code I would like to explain my idea. This question is similar to the probability questions that we used to study at high school, so I will solve it in the same way. I will use your numbers as well. So consider that you have a box that has 23 Red balls, 85 Green balls, 10 Yellow balls, and 50 Blue balls. All these balls are in one box and you have to randomly select one ball from the box, therefore the probability of Red is 0.23, Green is 0.85...

Here is my box of colored balls:

char apples[] = {'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y', 'r', 'g', 'g', 'r', 'g', 'g', 'r', 'g'};

You notice that I distributed the balls in the array using a special distribution. Well just imagine the box example using your numbers. You have 10 Yellow balls vs 85 Green ones, this means I expect to see in the box next to every 1 Yellow ball 8 Green ones, and in the same way I expect to see also 5 Blue and 2 Red. And since Green is most probable I expect to see it first. Therefore you can see that my array has the following pattern:

'g', 'g', 'g', 'g', 'g', 'g', 'g', 'g', 'b', 'b', 'b', 'b', 'b', 'r', 'r', 'y',

Which is for every 1 Yellow, 8 Greens, 5 Blues, 2 Reds. Since there are some more Reds and Greens I added them at the end of the array.

Now the process is very simple, since the set contains 168 balls I made a loop that runs 168 times and each time it generates a number from 0 to 167. I use this number is the index of the array apples and I see which ball I get.

int counters[4] = {0, 0, 0, 0};
int x;
for(int i=0; i<168; i++)
{
    x = arc4random()%168;
    if(apples[x] == 'r') counters[0]++;
    else if(apples[x] == 'g') counters[1]++;
    else if(apples[x] == 'y') counters[2]++;
    else if(apples[x] == 'b') counters[3]++;
}

NSLog(@"Red:    %i%%", counters[0]);
NSLog(@"Green:  %i%%", counters[1]);
NSLog(@"Yellow: %i%%", counters[2]);
NSLog(@"Blue:   %i%%", counters[3]);

Here are sample outputs of the program on different executions:

2013-07-04 19:48:54.557 DOS[798:707] Red:    24%
2013-07-04 19:48:54.560 DOS[798:707] Green:  78%
2013-07-04 19:48:54.562 DOS[798:707] Yellow: 11%
2013-07-04 19:48:54.563 DOS[798:707] Blue:   55%

2013-07-04 19:49:04.899 DOS[811:707] Red:    21%
2013-07-04 19:49:04.901 DOS[811:707] Green:  81%
2013-07-04 19:49:04.905 DOS[811:707] Yellow: 9%
2013-07-04 19:49:04.906 DOS[811:707] Blue:   57%

2013-07-04 19:49:15.243 DOS[824:707] Red:    20%
2013-07-04 19:49:15.246 DOS[824:707] Green:  89%
2013-07-04 19:49:15.246 DOS[824:707] Yellow: 8%
2013-07-04 19:49:15.247 DOS[824:707] Blue:   51%

You can play with the array as you like to enhance the results.

Answer 3

one possible solution is to add the items (probability * precision) times into the array and use random on it.

Else you can sum your probability and define areas

double max = (red.probability + green.probability + yellow.probability 
+ blue.probability) * 100.f;

int random = arc4random()%(int)max;

if(random < red.probability * 100)
    return red;
else if(random < (red.probability + blue.probability) * 100)
    return blue:
...

and so on.

also can create a for loop for this :)

update

double max = (red.probability + green.probability + yellow.probability 
+ blue.probability) * 100.f;
// max = (0.23 + 0.85 + 0.1 + 0.5) * 100; // = 1.68 * 100 = 168 

int random = arc4random()%(int)max;

if(random < red.probability * 100) // area 0 - 23
    return red;
else if(random < (red.probability + blue.probability) * 100) // area 24 - 108
    return blue:
...

and in loop you can hold a currentValue variable

double max = (red.probability + green.probability + yellow.probability 
+ blue.probability) * 100.f;
// max = (0.23 + 0.85 + 0.1 + 0.5) * 100; // = 1.68 * 100 = 168 

int random = arc4random()%(int)max;
int currentValue = 0;

for(Apple *apple in array)
{
    currentValue += (int)(apple.probability * 100.f);
    if(random <= currentValue)
        return apple;
}

just try this with test values and if it's not working as you wish, tell me what you miss :)