[NBLUG/talk] Request for help--how to program shuffling

[Andru Luvisi]

On Tue, 20 May 2003, Steve Zimmerman wrote:
[snip]
> What I'm really after is a program that can take 52 things
> and randomly shuffle them *every time I run it*.  Any ideas?
[snip]

You left out the random_shuffle() function, which seems to be where the
problem is.

Here is a standard way to shuffle an array.  Sorry, I can't remember this
algorithm's official name and my references are at work.  If you are
creating an online casino you will want a much better random number
generator.

#include <stdlib.h>

srand(time()); /* Only call once in the run of the program. */

for(i = 51; i > 0; i--) {
  /* Only run 51 times.  No decisions to make on the last card. */

  new_item = rand() % (i + 1);  /* To avoid all bias, discard anything
                                   larger than
                                   RAND_MAX - (RAND_MAX % (i + 1)) - 1
                                   On systems other than Linux you might
                                   want to do this differently.  See the
                                   man page for rand(3).
                                 */

  if(new_item == i) /* I don't know if this gains or loses speed. */
    continue;

  temp              = vector1[new_item];
  vector1[new_item] = vector1[i];
  vector1[i]        = temp;
}

The basic idea is that for each position in the deck you select a random
card from the unfinished portion of the deck.  Assuming a truly random
selection (I know, I know, big assumption) this gives an equal probability
for every possible order of the cards.  Using the rand() function, which I
am guessing has no more than 32 bits of internal state, will give you at
most 4294967296 possible orders of the cards, as opposed to the 52
factorial
(80658175170943878571660636856403766975289505440883277824000000000000)
possible orders a deck of cards can be in.

The naive approach is to pick two random cards and swap them, and keep
doing this lots and lots of times.  Assuming a perfect random number
generator, this does not give all possible orders of the cards with equal
probability.  Sorry, I do not remember the proof.

Best of luck,
Andru
-- 
Andru Luvisi, Programmer/Analyst


Quote Of The Moment:
  "The finished...expert considers nothing too trivial that in any way
  contributes to his success..."
  
          - S. W. Erdnase