Random Numbers

Need a program to find non-repeating random numbers

Page 1 of 1

3 Replies - 3881 Views - Last Post: 19 June 2006 - 12:24 PM Rate Topic: -----

#1 Bibby  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 17-June 06

Random Numbers

Posted 17 June 2006 - 09:12 AM

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 non-repeaters, 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.

Is This A Good Question/Topic? 0
  • +

Replies To: Random Numbers

#2 Videege  Icon User is offline

  • rÍvant.toujours
  • member icon

Reputation: 6
  • View blog
  • Posts: 1,413
  • Joined: 25-March 03

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 :D) is to instead store potential and non-potential 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 0-200, and you found that you already picked all the numbers between 0-132, pick between 133-200.

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 non-repeating 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 1-1000
}
//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 1-1000.
}
}



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 :D). Shuffling your set of numbers is probably a much more efficient and speedy method to what you want.
Was This Post Helpful? 0
  • +
  • -

#3 msg555  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 9
  • View blog
  • Posts: 136
  • Joined: 04-May 06

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

Was This Post Helpful? 0
  • +
  • -

#4 skyhawk133  Icon User is offline

  • Head DIC Head
  • member icon

Reputation: 1877
  • View blog
  • Posts: 20,284
  • Joined: 17-March 01

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.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1