I have seen this question pop up on the board from time to time about generating random number values, in a given range, but not repeating any of the values. It is simple enough to create your standard number generator, and even simple to test the value it generates against previously selected values, but that method has always been a “brute force” type of approach and can be a nightmare if you have a large number of values and 99% of them have already been chosen. Are you going to let your program sit there generating thousands of numbers it can’t use until you hit that one remaining number? I talk about a way to get around that and improve some efficiency of number generating in C++…. on this episode of the Programming Underground!
The approach involves creating an array of values. These can be in a given range or could just be any array of values from which you want to pick your numbers from. In the example below I generate a list of sequential values so that you can see the results at the end showing all numbers were indeed chosen and that we have full coverage of the number pool. These values are then sent through a quick shuffle function which spins around a loop an arbitrary number of times swapping random slots with one another. This would be the equivalent of putting a deck of cards on a table and with your hands spreading them around, then putting them back into a deck. You may have seen that done on those professional poker tournaments. Or at your own poker table as that cute girl steals all your chips. 😉
Once the array of values have been shuffled with a good number of swaps, we have our numbers jumbled randomly all around the array. We can then simple pluck (aka pop) off a value from the array and use it as a randomly generated number in our program. Whenever you need the new random number, you pop off another value until the array is exhausted…. meaning you have randomly chosen all the values in the pool.
The great thing about this process is that it can be scaled quite a bit. There is still a bit of a performance hit with very large arrays due to the number of swaps, but you could essentially replace my shuffle with any quick, good timing level algorithm for swapping. Even with this small hit, you can typically gauge how long it will take based on the array size and it can be significantly faster than attempting to generate the last number of an array that might consist of thousands of values.
So here is how it works….
// time.h needed for our time function in the srand() call.
#include <iostream>
#include <time.h>
using namespace std;
void shuffle(int[],int);
int main()
{
int min, max;
// Prompt user for two integer values to specify a range.
cout << "Enter minimum integer value of number range: ";
cin >> min;
cout << "Enter maximum integer value of number range: ";
cin >> max;
// If the values for the range was reversed, swap them.
if (max < min) {
int temp = min;
min = max;
max = temp;
}
int range = (max - min);
// Create our new array of size "range"
int *values = new int[range];
// Load some counting values into our array
for (int i = 0; i <= range; i++) {
values[i] = min + i;
}
// Now shuffle the array values randomly.
shuffle(values,range + 1);
// Spit out the values
for (int i = 0; i <= range; i++) {
cout << "Next random value: " << values[i] << endl;
}
return 0;
}
void shuffle(int values[], int size) {
// Seed our random number generator.
srand((int)time(NULL));
// Create large number of swaps
// This example takes the size and times it by 20 for the number of swaps
for (int i = 0; i < (size * 20); i++) {
// Generate random values for subscripts, not values!
int randvalue1 = (rand() % size) + 0;
int randvalue2 = (rand() % size) + 0;
int temp = values[randvalue1];
values[randvalue1] = values[randvalue2];
values[randvalue2] = temp;
}
}
Again the example is very simple and straight forward. We ask the use for two numbers and generate an array that is a sequential range of values. So if we enter 2 and 9 we are going to get an array with values 2 – 9. It is then sent through our shuffle() function for shuffling. Based on the size of the range, we setup a for loop to swap values around… mixing up the values. After the shuffle, we have an array with our numbers randomly seated into various positions. It is just a matter of plucking off the value (you could start from the bottom or top if you like) and spit out random numbers…. none of which will be repeated until the pool is exhausted.
Read the in code comments to see how this process works and feel free to enhance the example any way you like. As I briefly mentioned before, you could replace the shuffle with any algorithm you want to mix the values as long as you don’t introduce any new values to your pool after shuffling. If your pool of numbers did have a repeat value, each value would be considered unique in this process. So if the number 9 was repeated 3 times, this process would generate 9 three times as well, but each 9 would be considered its own value.
You could use this process for letters, strings, doubles, or even pointers to objects. It is a great little helper tactic that you can employ in your masterful creations. I hope you like it and thank you again to all those who read my blog. I appreciate the interest and support.
If you would like me to cover some topic in my blog (and it hasn’t already been covered), ask those questions on the board. I may read it and expand on the answer. Better written the question, the more likely I am to cover it. Thanks again!
🙂
