"Weighted" random number generator

Question

I'm currently using the below code to grab a random element from an array. How would I go about changing the code so that it returns an element weighted on the percentage that I want it to come up? For example, I want the element at index 0 to come up 27.4% of the time, but the element at index 7 to come up only 5.9% of the time.

NSArray *quoteArray = @[    @"quote1",    @"quote2",    @"quote3",    @"quote4",    @"quote5",    @"quote6",    @"quote7",    @"quote8",    ];    

NSString *quoteString;

int r = arc4random() % [quoteArray count];
if(r<[rewardTypeArray count])
    quoteString = [quoteArray objectAtIndex:r];

Answer 1

I would use an array of float (wrapped into NSNumber) objects.

Every object represents a percentage.In this case you would have an array of 8 objects:

Object 1: @27.5 ;

...

Object 7: @5.9 .

Then you get a random number from 1 to 100. If you want more precision you can also get a random number with the decimal part, and the precision doesn't influence the efficiency and neither the memory used.

Then when you get the number you iterate through all the array, keep track of the index and the percentage that you have. You use a float to sum all the percentages met and you stop only when the total percentage is greater on equal that the one that you have.

Example

NSArray* percentages= @[ @27.4 , ... , @5.9];
float randomNumber= arc4random_uniform(100) + (float)arc4random_uniform(101)/100;  
NSUInteger n=0;
float totalPercentage= 0.0;
for(NSUInteger i=0; i<percentages.count; i++)
{
    totalPercentage+= [ percentages[i] floatValue ];
    if( totalPercentage >= randomNumber)  // This case we don't care about
                                          // the comparison precision
    {
        break;
    }
    n++;
}
// Now n is index that you want