I would like to ask you for a little programming assistance. I teach computer programming at a high school. My classes often work with random numbers. I have a small problem I haven’t been able to solve. We can generate random numbers that repeat, like dice rolls, but when we try to simulate nonrepeaters, like lottery drawing, it gets too slow once you get beyond maybe 100 numbers. My strategy has been to generate a number, compare it to the previously generated ones, and if its already been picked, throw it back and try again. By the time I get to the last numbers of a large (say 1000 or more) set of numbers it takes many tries to find the ones that are left and is way too slow. Can someone give me an idea how to avoid this problem? Thank you.
3 Replies  4017 Views  Last Post: 19 June 2006  12:24 PM
Replies To: Random Numbers
#2
Re: Random Numbers
Posted 17 June 2006  09:41 AM
Well, like you said, the larger the range of numbers that you start with, the longer it's going to take to randomly generate them all.
If you're already storing previously generated numbers, a possible solution that springs to mind (though, I just woke up ) is to instead store potential and nonpotential domains within your original boundary. For example, you could design a function that checks to see if certain sets of sequential numbers are already chosen, and if they are, you modify the range of numbers that you are generating random numbers for. So if you wanted to find all the random numbers between 0200, and you found that you already picked all the numbers between 0132, pick between 133200.
Of course, this solution will probably slow things down even further because you're not always going to have nice ranges like that, and of course dynamically narrowing your range actually skews the randomness of your series.
So...I'm at a loss here. Aha! Never mind. Because you are trying to generate nonrepeating random numbers within a defined range, you might be better off doing a shuffle of sorts than actually generating the numbers. The standard library has an excellent way of doing this via the random_shuffle() function. View below:
random_shuffle() is a function that is type generic, being part of the STL; its two parameters are simply pointers to the beginning of the input data and then one byte past the end of the data. Because an int usually occupies 4 bytes of memory, i could have done shuffledNumbers+(1000*4), but to be far more safe, it is better to do sizeof(int)*1000 so it can work across different compilers, etc.
So there you have it (sorry about the length of this post ). Shuffling your set of numbers is probably a much more efficient and speedy method to what you want.
If you're already storing previously generated numbers, a possible solution that springs to mind (though, I just woke up ) is to instead store potential and nonpotential domains within your original boundary. For example, you could design a function that checks to see if certain sets of sequential numbers are already chosen, and if they are, you modify the range of numbers that you are generating random numbers for. So if you wanted to find all the random numbers between 0200, and you found that you already picked all the numbers between 0132, pick between 133200.
Of course, this solution will probably slow things down even further because you're not always going to have nice ranges like that, and of course dynamically narrowing your range actually skews the randomness of your series.
So...I'm at a loss here. Aha! Never mind. Because you are trying to generate nonrepeating random numbers within a defined range, you might be better off doing a shuffle of sorts than actually generating the numbers. The standard library has an excellent way of doing this via the random_shuffle() function. View below:
#include <iostream> #include <algorithm> //the header file for random_shuffle() using namespace std; void main() { int shuffledNumbers[1000]; //to hold our shuffled up numbers for (int i=0; i < 1000; i++) { shuffledNumbers[i] = i+1; //set our array to contain the numbers 11000 } //now we will shuffle all the values in the array random_shuffle(shuffledNumbers, shuffledNumbers+(sizeof(int) * 1000)); for (int c=0; c < 1000; c++) { cout << shuffledNumbers[c] << endl; //this loop will output a random (or shuffled, in this case) series of //numbers from 11000. } }
random_shuffle() is a function that is type generic, being part of the STL; its two parameters are simply pointers to the beginning of the input data and then one byte past the end of the data. Because an int usually occupies 4 bytes of memory, i could have done shuffledNumbers+(1000*4), but to be far more safe, it is better to do sizeof(int)*1000 so it can work across different compilers, etc.
So there you have it (sorry about the length of this post ). Shuffling your set of numbers is probably a much more efficient and speedy method to what you want.
#3
Re: Random Numbers
Posted 19 June 2006  12:22 PM
Another solution would be to generate a random number 'N' 0 through the number of valid possibilities  1. Then find the Nth smallest valid possibility. In this example elements is redundant because elements[i] == i but elements can be whatever you want, even other data types.
//Declare arrays int elements[NUM_ELEMENTS]; bool isValid[NUM_ELEMENTS]; //Initialize arrays for(int i = 0; i < NUM_ELEMENTS; i++) { elements[i] = i; isValid[i] = true; } //we are going to draw NUM_ELEMENTS numbers for(int i = 0; i < NUM_ELEMENTS; i++) { //Pick a random number 0 through the number of valid elements left int x = rand() % (NUM_ELEMENTS  i); //Find the xth valid number int j = 0; while(x >= 0) { if(isValid[j++]) x; } j; //element j was chosen isValid[j] = false; cout << elements[j] << endl; }
This post has been edited by msg555: 19 June 2006  12:32 PM
#4
Re: Random Numbers
Posted 19 June 2006  12:24 PM
msg55, thanks for helping out!
Anyone else have another solution to share? It's interesting to see the different ways to accomplish the same task.
Anyone else have another solution to share? It's interesting to see the different ways to accomplish the same task.
Page 1 of 1
