Re: Best way to get a non-repeating random number?
Re: Best way to get a non-repeating random number?
- Subject: Re: Best way to get a non-repeating random number?
- From: Boyd Collier <email@hidden>
- Date: Tue, 14 Apr 2009 16:30:04 -0700
Here's what I've been using for shuffling an array of ints. It appears
to work quite well and is very simple and fast.
/*
* shuffle
*
* This function is from http://www.stanford.edu/~blp/writings/clc/shuffle.html
* Copyright ¨© 2004 Ben Pfaff
*
* BDC made change to add argument to allow new seed to be used for
each call of shuffle
*
* Arrange the n elements of array of ints in random order. Only
effective if n is much smaller than RAND_MAX;
* if this may not be the case, use a better random number generator.
*/
void shuffle(int *array, size_t n, char new_seed) // set new_seed to 0
if same seed is to be used with each shuffle (resuling in the
//same sequence of values with each shuffle)
{
if (new_seed)
srandom(time (0));
if (n > 1) {
size_t i;
for (i = 0; i < n - 1; i++) {
size_t j = i + random() / (RAND_MAX / (n - i) + 1);
int t = array[j];
array[j] = array[i];
array[i] = t;
}
}
}
// this is a quick example showing how to use shuffle
int main (int argc, const char * argv[]) {
int arraysize = 500; // an arbitrary choice for the example
int *myArray = (int *)malloc((size_t)(arraysize*sizeof(int)));
int i;
for (i = 0; i < arraysize; i++)
myArray[i] = i+1;
shuffle(myArray, arraysize, 0);
for (i = 0; i < arraysize; i++)
printf("%i \n", myArray[i]);
free(myArray);
return 0;
}
Ricky,
Have you looked at SFMT, which is a new variant of Mersenne Twister?
I've not tried to implement it, but it looks interesting. See
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html
Boyd
On Apr 14, 2009, at 1:32 PM, Ricky Sharp wrote:
On Apr 13, 2009, at 7:58 PM, Eric E. Dolecki wrote:
For an example I might want to generate numbers from 1 to 10 over
and over.
All I want to do is when I generate a new number is not allow it to
equal
the previously held value. I can imagine a few approaches but I
just wanted
to make sure I was using the most accepted way of doing it.
Coming in late to this thread...
Personally, for all things random, I now use the Mersenne Twister
algorithm. You can license that for free; just put in the specified
acknowledgement text somewhere in your app/docs.
And, for shuffling, I use the Fisher-Yates algorithm.
For the specific problem above, you sort of have a "modified pick
without replacement" scenario.
Assume you start with an array of 10 values where the values are set
from 1 to 10.
The first time you pick a number, you randomly generate the index of
the number (so 0..9).
That first value then becomes "picked". Your array is then modified
to contain the 9 remaining values.
The 2nd, 3rd, etc. time you pick a number, you basically just pick
from the nine remaining indexes. Then, put back the item you picked
in the previous iteration and pull out the item you picked this
iteration.
___________________________________________________________
Ricky A. Sharp mailto:email@hidden
Instant Interactive(tm) http://www.instantinteractive.com
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden
_______________________________________________
Cocoa-dev mailing list (email@hidden)
Please do not post admin requests or moderator comments to the list.
Contact the moderators at cocoa-dev-admins(at)lists.apple.com
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden