|
Phoenix
|
You know it happens. You're writing a program and you need a random sequence, but you need it to never repeat the same number twice. The problem is, as you use up numbers your choices become smaller and smaller, so how do you avoid a "while" loop that approaches infinity? You can run a random number generator forever and never fill in that last value. The larger the range, the worse this problem becomes. Well, here's a useful function that might help with this problem.void randomize( void ){
#define MAX_RANDOM_COUNT 256;
int count[MAX_RANDOM_COUNT];
int randomArray[MAX_RANDOM_COUNT];
int num;
int i;
for (i = 0; i < MAX_RANDOM_COUNT; i++){
count[i]=i;
}
for (i = MAX_RANDOM_COUNT -1; i > -1; i--){
num = (abs)(crandom() * i);
randomArray[i] = count[num];
count[num] = count[i];
}
}
So what does this do? Generating non-repeating number sequences requires decaying the range over the duration of the sequence generation, the idea being to kick out whatever number has already been used so it's no longer included in the possible random choices. The easiest way to do this is to create two variable arrays of equal size. You set the first array up (count, in this case) so that each entry is equal to it's position, ie: count[0] = 0; count [1] = 1; count[2] = 2; as is done in the first loop in the above function. Just a simple numeric sequence.
Next, we want to set up our actual array to store our random numbers. What we're going to do is cycle through randomArray's positions using the loop, and set each position equal to a value stored in the count array. We grab the position from the count array randomly as indicated by "num", which is generated randomly but CAN repeat. Here's the clever part, and why this works. We want to ensure the "used up" number is always the number decayed out. We run a reverse loop, counting DOWN from our upper limit, and we shrink the upper bound of the random by matching our loop. (Note that I used from (MAX_RANDOM_COUNT -1) to -1 because the first position in the array is randomArray[0] and the last is randomArray[255], not 256. We don't want to set a non-existant array entry!) Once we grab the value of count[num] and stuff it into randomArray, we set the value of count[num] equal to the value stored at count, since count will no longer be available on the next cycle. Why this is so may not be entirely clear from the syntax, so I will elaborate.
The loop starts at 255 (arbitrary number we used as the upper bound), so randomArray[255] is the first value that gets set. Also, count[255] is the first position that is going to be eliminated. Say our random "num" ends up being 42. We set randomArray[255] = count[42], which also happens to be equal to 42. Now, count[255] is going to be eliminated, and 42 is used up, so we want to copy the value of count[255] into count[42], so count[42] is now equal to 255. We know we did not use the number 255, and since count[255] can never come up again once the loop advances, we stuff it into count[42] since 42 has been used. This eliminates the number 42 completely since it has been overwritten by another number. The number we did not use, 255, is still available since it is now stored in count[42], and since count[255] cannot ever show up again we eliminate the chance of 255 being availiable twice. Therefore, the only number truly "lost" in this process is 42, which is the one we wanted to use up in the first place.
Let's take this a step further. We advance to randomArray[254], and "num" turns up 42 yet again. Well, count[42] is now 255, so randomArray[254] is now set equal to 255. We now set count[42] equal to count[254], which is still 254. Now the number 255 has been overwritten as well, with count[42] now equal to 254. We cycle count[254] out this time around, so the number 254 is again only available once.
Well, what happens if randomArray[253] comes up, and "num" turns up 253? Then randomArray[253] is then set to 253, count[253] is already set to 253, so 253 will be cycled out and there's no problem.
The idea is that whatever number is in the position of count can never ever be repeated, so as long as we set count[num] equal to whatever is in count we ensure the non-repeatability of the value stored in count[num]. As a result this is a very efficient function, using only two "for" loops - one to initialize the count array, and one to set the randomArray.
|
