PDA

View Full Version : Random numbers with exceptions



dabeav
09-12-2001, 12:52 PM
Alright folks here is my question.

I want use random numbers in a range of 1-50.
I know i want to use something like this

int value

randomize();
{ value = random(50);}

etc;

but my problem comes into effect when I want to restrict individual numbers as there used out of the pool of 50, so that I never use the same number twice untill all 50 have been used up.
I could do this will alot of random numbers being picked, and then checking them against a list of already used values, but as I move through the list the proccessor time to keep picking and checking numbers grows greatly.
What I really want to do is simply tell the computer not to even consider the already chosen numbers in its random number calculations. Any suggestions?

Humus
09-12-2001, 02:49 PM
Not sure if this is a good algorithm, but I'm thinking along the line of puting the 50 numbers into a list, the shuffle the list, then pick numbers from the top of the list to the end. Then of course the shuffle step may not be cheap, but at least it's garantueed to terminate within a certain time, O(N) I think will be possible.

My next though is that a hash table may help you ... but I'm not sure, it's like 02:00 here and I'm quite tired ... http://www.opengl.org/discussion_boards/ubb/smile.gif

*Humus goes to sleep*

dabeav
09-12-2001, 05:53 PM
First, im not sure if that would work for my perticular task, but just incase i can make it work. Any one have any ideas as to how to shuffle the list, and then retrieve the data. Once again, without any repeats.

Bob
09-13-2001, 03:19 AM
There was an old Code of the Day over at Flipcode a while ago. It's a class for random numbers with a gaussian distribution. Might sound irrelevand in thÝs case, but the source includes a random number pool generator. Very clever and very easy to understand.

You find the it here (http://www.flipcode.com/cgi-bin/msg.cgi?showThread=COTD-GaussianNumberClass&forum=cotd&id=-1) .

Humus
09-13-2001, 04:28 AM
I quickly threw together this code. It does solve the problem and the shuffle executes in O(n).




#include <stdlib.h>
#include <stdio.h>
#include <conio.h>

int rands[50];


int main(){
int i,j,tmp;

// Generate the numbers
for (i = 0; i < 50; i++){
rands[i] = i;
}

do {
// Shuffle
for (i = 0; i < 50; i++){
j = rand() % 50;

tmp = rands[j];
rands[j] = rands[i];
rands[i] = tmp;
}

// Check what it looks like http://www.opengl.org/discussion_boards/ubb/smile.gif
for (i = 0; i < 50; i++){
printf("%d ", rands[i]);
}
printf("\n\n", rands[i]);

tmp = getch();

} while (tmp != 27);



return 1;
}

dabeav
09-13-2001, 02:14 PM
Thank you for your input, the code does work very well for my purpose, I did change it though to seed a time value into the mix to come up with different random numbers at each boot of the program. But my next question is what are the 2 lines at the bottom of the program for?

tmp = getch();
while (tmp != 27);

what is getch();
and why does tmp not want to equal 27?

any ideas?
i just want to make my code compleatly understandable

Humus
09-13-2001, 02:31 PM
Oh, that's just so you can close the program by pressing ESC. getch() read a character from the keyboard, and the ESC button has ASCII code 27. http://www.opengl.org/discussion_boards/ubb/smile.gif

dabeav
09-13-2001, 02:55 PM
Thank you so much once again, all of my work is done on an open platform basis, so all of my keyboard handlers are glut based, so that is where my confussion played in. Thank you so very much for your help.