Hi, I'd like to pick a value from an array which is sorted using a priority value, 0-100.

However, I'm looking for a way that returns a value in the array with a higher priority more frequently.

Say my array has 5 values:

[100, 50, 10, 3, 1]

I would like the value "100" to be returned more often than "50". The value of "1" should rarely be chosen.

Two ways I think I can solve it, but not exactly ideal or efficient:

1. Put more of the higher priority values in the array: [100, 100, 100, 100, 100, 50, 50, 50, 50, 10, 10, 10, 3, 3, 1]

2. Multiply a random number (t) by a curve: http://easings.net/#easeInQuint and use that as the index (x).

Just wondering if there's a better way?

Thanks

Your second option is possible if it is sufficient to only approximate the distribution of the individual elements. This is equivalent to generating random numbers with a different distribution, you example is biased towards the start of the array so a Laplacian distribution could make sense.

Another option that allows for fully arbitrary and individual weights is to keep a separate vector of weights corresponding to each element. Sum all the weights and generate a random number from 0 to to the sum. Loop through the array to find the point where the cumulative sum of all previous weights becomes greater than then generated random number.

An optimization on that variant is to keep an array of cumulative weights instead of the weights themselves. The last element is the sum of all elements, and you can now use a binary search algorithm to find the random number more efficiently.

Thanks, turns out I'm looking for a "weighted random" function.

http://stackoverflow.com/questions/1761626/weighted-random-numbers

Out of curiosity, what is it you're trying to model? Sometimes the domain can influence the best approach to dealing with probability densities.

Match 3 game. I'd like certain types of "tiles" or "gems" to be selected more frequently.

{{100, 10},
 {50 , 10},
 {10 , 5},
 {3  , 2}}

{{100, 10},
 {50 , 20},
 {10 , 25},
 {3  , 27}}

The c++11 way: http://en.cppreference.com/w/cpp/numeric/random/discrete_distribution