-
April 2nd, 2009, 01:34 AM
#1
Shuffling an array
I have created a function that is supposed to shuffle the values in an array, I am having issues though - it doesn't seem to shuffle very well and I'm looking for some insight about how to go about it better.
Code:
void shuffle(int* a, int size){
srand((unsigned)time(0));
for (int i = 0; i < (size-1); ++i) {
int r = i + (rand() % (size-i)); // Random remaining position.
int temp = a[i]; a[i] = a[r]; a[r] = temp;
}
}
By not shuffling very well, I mean that I will frequently get the same result twice in a row.
EDIT
I also came up with this:
Code:
void shuffle(int* a, int size){
srand((unsigned)time(0));
for (int i = 0; i < (size-1); ++i) {
double x=rand()/(RAND_MAX+1.0);
int r = (int)(x * (size - 1));
int temp = a[i]; a[i] = a[r]; a[r] = temp;
}
}
it works well. Still, I'd like to see suggestions if anyone has any.
Thanks!
Last edited by Lang; April 2nd, 2009 at 01:43 AM.
-
April 2nd, 2009, 02:41 AM
#2
-
April 2nd, 2009, 03:31 AM
#3
Re: Shuffling an array
Still, I'd like to see suggestions if anyone has any.
Use one that's already been written and debugged and part of the C++ specification.
std::random_shuffle
"It doesn't matter how beautiful your theory is, it doesn't matter how smart you are. If it doesn't agree with experiment, it's wrong."
Richard P. Feynman
-
April 2nd, 2009, 04:06 AM
#4
Re: Shuffling an array
Originally Posted by Lang
I have created a function that is supposed to shuffle the values in an array, I am having issues though - it doesn't seem to shuffle very well and I'm looking for some insight about how to go about it better.
Code:
#include <algorithm>
void shuffle(int* a, int size)
{
std::random_shuffle(a, a + size);
}
Regards,
Paul McKenzie
-
April 2nd, 2009, 04:43 AM
#5
Re: Shuffling an array
Perfect shuffle is the way to go in case you don't want to use STL.
Thanks for your help.
-
April 2nd, 2009, 04:58 AM
#6
Re: Shuffling an array
I also recommend using std::random_shuffle.
The cause of your problem is the srand call at the beginning of your shuffle function. It initializes the rng seed to a pseudo random value. Identical seeds produce identical "random" numbers, so you have to make sure you initialize the seed with different numbers. time( 0 ) returns the number of seconds elapsed sind 1.1.1970, and if your shuffle function takes less than one second the RNG seed may be initialized with the same value it was initialized the call before, resulting in identical random numbers.
Move srand() to the main() function and your problem should be fixed.
- Guido
-
April 2nd, 2009, 11:48 AM
#7
Re: Shuffling an array
using random_shuffle() I always get the same shuffled array returned.
-
April 2nd, 2009, 12:17 PM
#8
Re: Shuffling an array
Originally Posted by Lang
using random_shuffle() I always get the same shuffled array returned.
You still need to seed with srand(), or provide your own random number generator to random_shuffle().
-
April 2nd, 2009, 01:49 PM
#9
Re: Shuffling an array
Originally Posted by Lang
using random_shuffle() I always get the same shuffled array returned.
if you use the random_shuffle() implementation that comes with g++ 3.3 you have to implement your own random generator. Calling srand() doesn't help to seed the default random generator.
This was fixed using g++ 4.x .
Kurt
-
April 3rd, 2009, 04:40 AM
#10
Re: Shuffling an array
Thanks for your help.
Tags for this Thread
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|