Shuffling an array
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: Shuffling an array

  1. #1
    Join Date
    Jan 2009
    Posts
    16

    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() &#37; (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.

  2. #2
    ovidiucucu's Avatar
    ovidiucucu is offline Moderator/Reviewer Power Poster
    Join Date
    Feb 2003
    Location
    Iasi - Romania
    Posts
    7,994

    Re: Shuffling an array

    [ Moved thread ]
    Ovidiu Cucu
    "When in Rome, do as Romans do."
    Visit: Microsoft Virtual Academy
    Follow: https://twitter.com/#!/ovidiucucu
    My blog: http://codexpert.ro/blog/author/ovidiu-cucu/

  3. #3
    Join Date
    Jul 2002
    Location
    Portsmouth. United Kingdom
    Posts
    2,694

    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

  4. #4
    Join Date
    Apr 1999
    Posts
    27,418

    Re: Shuffling an array

    Quote Originally Posted by Lang View Post
    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

  5. #5
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: Shuffling an array

    Perfect shuffle is the way to go in case you don't want to use STL.
    Thanks for your help.

  6. #6
    Join Date
    Nov 2006
    Location
    Essen, Germany
    Posts
    1,344

    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.

  7. #7
    Join Date
    Jan 2009
    Posts
    16

    Re: Shuffling an array

    using random_shuffle() I always get the same shuffled array returned.

  8. #8
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,196

    Re: Shuffling an array

    Quote 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().
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  9. #9
    Join Date
    Oct 2002
    Location
    Austria
    Posts
    1,284

    Re: Shuffling an array

    Quote Originally Posted by Lang View Post
    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

  10. #10
    Join Date
    Apr 2007
    Location
    Mars NASA Station
    Posts
    1,436

    Re: Shuffling an array

    Good info.
    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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center