Card Shuffling algorithm

I'm interested, so I'm listening.  I know cards.dll does it...but no clue HOW.

~Aaron

i dun know existing algo ..

but lets try this ...

hows abt making a circular linked list of 52 nodes ..

now top is the head pointer of ur list .

fill these 52 nodes with random values ( from cards ) ..in start u have random data , for shufling u just need to change the pointer positions ..of the chunk to be moved to the proper position ..rite !!!!

i guess we can easily implement this thing !!!

here random data selection can be a function of time ...

Here are the 2 algorithms I have tried:

for (i = 0; i<52; i++)
{
  int k = rand() % 52;
  swap (card[i],card[k]);
}

or

for (i = 51; i>=0; i--)
{
  int k = rand() % (52-i);
  swap (card[i],card[k]);
}


I'm not satisfied with either, since I seem to see the same numbered cards come up in a row, fairly often. ( for example, Flip one, see a 7 of hearts, flip the next card, see a 7 of clubs )

You see the same sequences because you're not seeding rand().  Take a look at srand() to see if the one you use will give you a more random seed for rand().  You may want to consider a seed based on milliseconds past midnight, or something like that.

Assuming a truely random rand (generally not a good assumption)
The second algoritithm would be a fair shuffle, the first would not be fair.

The accepted answer gives a biased shuffle even assuming a perfect rand

how is it biased?

~Aaron

For one thing, it tends to produce more runs than average.
while (used[posn]) posn = ++posn % Deck_Size;
is more likely to end up at the end of a block of used posn's than elsewhere.
and fundamentally,
for (int s = int(Diamond); s <= int(Spade); ++s){ for (int c = int(Ace); c <= int(King); ++c){ posn = (posn + rand()) % Deck_Size;
would produce 52^52 equally lilkely shuffles given a perfect rand
but 52! does not divide 52^52 so some shuffles would turn up more often than others.
But
(unsigned)time(NULL) | 1
can only ever produce 2^31 possible seeds, (only 43200 possible seeds during a given day)
which is much less than 52! to start with, severely restricting the possible shuffles produced
A sharp player or clever algorithm can even exploit this nonrandomess to advantage.
On the other hand, you shouldn't rely too mugh on how satisfying the randomness seems to a human in judging the quality of a shuffle.  People are too good at picking out patterns that will always exist in a random sequence.
It's better to perform the appropriate statistical tests for the randomness properties you require.

Here's an suggestion from Donald Knuth.

Attach a random key to each card, sort on the keys, and discard the keys.

my example:
for (i=0;i<52;i++)
  R[i] = rand()%1000;
//mod by 1000 to get a more even distribution (will be between 100 and 999)
 
//bubble sort
for (i=0;i<52;i++)
  for (j=(i+1);j<52;j++)
     if r[i]>r[j]
     {
        swap r[i],r[j];
        swap card[i],card[j];
     }

I think this will work rather well.

Correction: don't mod the random number.

This question was awarded, but never cleared due to the JSP-500 errors of that time.  It was "stuck" against userID -1 versus the intended expert whom you awarded.  This corrects that and the expert will now receive these points, all verified.
Moondancer
Moderator @ Experts Exchange