Jump to content
  • Advertisement
heh65532

random selection of array elements

Recommended Posts

Hello,

I have a bit of programming dilemma which I cannot seem to solve my self.

What if I have an array of numbers and I want to randomly select entry from the array so that the higher the number in the array the more likely it gets picked?

For example array like this:

[1000,800,400,200]

Should have highest change of selecting the highest number (1000) and lowest change for the lowest number.

 

How to calculate this?

 

thanks!

 

Share this post


Link to post
Share on other sites
Advertisement

Sort the numbers, then define a non-uniform probability distribution. (Search for that and similar terms for examples.)

Share this post


Link to post
Share on other sites

A memory intensive way to go about it is:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#include <cstdlib>

int main(void)
{
    vector<long unsigned int> numbers;
    
    for(size_t i = 0; i < 1000; i++)
        numbers.push_back(1000);
    
    for(size_t i = 0; i < 800; i++)
        numbers.push_back(800);
    
    for(size_t i = 0; i < 400; i++)
        numbers.push_back(400);
    
    for(size_t i = 0; i < 200; i++)
        numbers.push_back(200);
    
    if(numbers.size() > RAND_MAX)
    {
        cout << "Need a better PRNG" << endl;
        return 0;
    }
    
    long unsigned int pseudo_random_number = numbers[rand() % numbers.size()];
    
    cout << pseudo_random_number << endl;
    
    return 1;
}
Edited by sjhalayka

Share this post


Link to post
Share on other sites

sjhalayka: You don't need to shuffle the array if you're picking from it randomly.

The main information missing from the question is a rigorous definition of the desired distribution. How much more likely should one number be picked over another, and what decides that?

Usually the simple approach here is to have an explicitly-weighted random selection. The standard algorithm for this is roulette wheel/fitness proportionate selection. (The Java 'rouletteSelect' function on that page is probably the most sensible implementation.)

Share this post


Link to post
Share on other sites

@Lactose I googled one article but no help yet from there, will continue looking.

@sjhalayka Thanks that works! I wonder if there is another approach that's not so heavy... 

@Kylotan The higher the number the higher the change of being picked.

 

Share this post


Link to post
Share on other sites

It's still not clear - are the numbers you're selecting also the exact proportions that you want them to be picked in? Or are the proportions different to the numbers?

Share this post


Link to post
Share on other sites
2 minutes ago, Kylotan said:

It's still not clear - are the numbers you're selecting also the exact proportions that you want them to be picked in? Or are the proportions different to the numbers?

proportions are different to the numbers. all I need is select just one number from the array as long as it's random.

Share this post


Link to post
Share on other sites

Right, so what I'm saying (and what Lactose said) is that you need to specify those proportions somehow. 'Higher' isn't enough information - how much higher, in each case? The roulette wheel selection method I linked to allows you to choose those proportions explicitly.

Share this post


Link to post
Share on other sites

Ok here's the deal, I have been working on code to do this but it doesn't seem right, I'm unsure if I got the math right.

I made sample program where there's no arrays but I'm trying to calculate the probability for each number. 100 / 100 for example should have 50% probability.

 

Or in another example max number being 100 the number 10 should have 10% change of being picked.

(max number just means the highest number found in array)

 

here's the program:

 

// Example program
#include <iostream>
#include <string>

using namespace std;

int maxNum = 100;

int main()
{
 for(float i = 0; i <= maxNum; i += 10)
 {
     float change = i / ((float)maxNum) / 2.0;
     
     cout << (int)i << " / " << maxNum << " = " << change << " " << ( int(100 * change)) << "% " << endl;
 }
}

 

Which outputs:

 

0 / 100 = 0 0% 
10 / 100 = 0.05 5% 
20 / 100 = 0.1 10% 
30 / 100 = 0.15 15% 
40 / 100 = 0.2 20% 
50 / 100 = 0.25 25% 
60 / 100 = 0.3 30% 
70 / 100 = 0.35 35% 
80 / 100 = 0.4 40% 
90 / 100 = 0.45 45% 
100 / 100 = 0.5 50% 

 

where the final (100 / 100) seems to be correct result but the five first calculations doesn't seem right. 10 / 100 should be 10% but I'm not sure if I got that part right.

 

any ideas how to make this work?

 

Edited by heh65532

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!