• Advertisement
Sign in to follow this  

Picking a random value from array with priority

This topic is 1048 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Edited by mr_malee

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
You can take the table of probabilities and transform it by computing partial sums.

{{100, 10},
 {50 , 10},
 {10 , 5},
 {3  , 2}}
turns into
{{100, 10},
 {50 , 20},
 {10 , 25},
 {3  , 27}}
Now take a random number 0 <= r < 27 and see where it fits in the table (using binary search, for instance).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement