Random selection of two values

Question

In my algorithm, I have two values ​​that I need to randomly select, but each of them must be selected a predetermined number of times.

So far, my solution has been to put the selection in the vector the correct number of times, and then shuffle it. In C ++:

// Example choices (can be any positive int) int choice1 = 3; int choice2 = 4; int number_of_choice1s = 5; int number_of_choice2s = 1; std::vector<int> choices; for(int i = 0; i < number_of_choice1s; ++i) choices.push_back(choice1); for(int i = 0; i < number_of_choice2s; ++i) choices.push_back(choice2); std::random_shuffle(choices.begin(), choices.end()); 

Then I save the iterator to choices , and whenever I need a new one, I increment the iterator and grab it.

This works, but it seems that there may be a more efficient way. Since I always know how many of each value I will use, I wonder if there is a more algorithmic way to do this, and not just store the values.

Answer 1

No need to use as much memory. You have two variables:

 int number_of_choice1s = 5; int number_of_choice2s = 1; 

Now just randomize:

 int result = rand() % (number_of_choice1s + number_of_choice2s); if(result < number_of_choice1s) { --number_of_choice1s; return choice1; } else { --number_of_choice2s; return choice2; } 

This scales very well with two million random calls.

Answer 2

You could write this a little easier:

 std::vector<int> choices(number_of_choice1s, choice1); choices.resize(number_of_choice1s + number_of_choice2s, choice2); std::random_shuffle(choices.begin(), choices.end()); 

Answer 3

A biased random distribution will preserve some order in the result set (the selection that was most selected has a smaller and lower chance of being selected further), which gives a biased result (especially if the amount of time you have to select the first value is large compared to the second value, you will get something like this {1,1,1,2,1,1,1,1,1,2}.

Here's a code that is very similar to code written by @Tomasz Nurkiewicz, but using a simple even / odd code that should give a 50/50 chance to pick any values.

 int result = rand(); if ( result & 1 && number_of_choice1s > 0) { number_of_choice1s--; return choice1; }else if (number_of_choice2s>0) { number_of_choice2s--; return choice2; } else { return -1; }