• C

# Card Shuffling algorithm

Is there a standard Card Shuffling algorithm that is guaranteed to give a good shuffle?
###### Who is Participating?

Commented:
Next is cards class for shuffling:
cards.hpp

/*
**  CARDS.HPP - Declare card classes
**
**  public domain by Bob Stout
*/

#ifndef CARDS__HPP
#define CARDS__HPP

const int Card_Error = -1;
const int Deck_Size  = 52;

typedef enum {Rank_Error = Card_Error, Ace = 1, Deuce, Trey, Spot_4, Spot_5,
Spot_6, Spot_7, Spot_8, Spot_9, Spot_10, Jack = 11, Queen = 12,
King = 13} cardRank;

typedef enum {Suit_Error = Card_Error, Diamond, Club, Heart, Spade} cardSuit;

class card
{
private:
cardRank rank_;
cardSuit suit_;

public:
card(void);
card(cardSuit s, cardRank r);
cardRank rank(void);
cardSuit suit(void);
void get_card(cardSuit &s, cardRank &r);
char *rankText(void);
char *suitText(void);
void set_rank(cardRank r);
void set_suit(cardSuit s);
void set_card(cardSuit s, cardRank r);
};

class deck
{
private:
class card card_[Deck_Size];
unsigned top;

public:
deck(void);
void shuffle(void);
void deal(class card &c);
int cards_left(void);
};
#endif // CARDS__HPP

Cards.cpp:

/*
**  CARDS.CPP - Playing card classes
**
**  public domain by Bob Stout
*/

#include <stddef.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "cards.hpp"

const char *suits[] = {"Diamonds", "Clubs", "Hearts", "Spades"};
const char *cards[] = {"Ace", "Deuce", "Trey", "4", "5", "6", "7", "8", "9",
"10", "Jack", "Queen", "King"};

inline card::card(void)
{
rank_ = Rank_Error;
suit_ = Suit_Error;
}

inline card::card(cardSuit s, cardRank r)
{
rank_ = r;
suit_ = s;
}

inline cardRank card::rank(void)
{
return rank_;
}

inline cardSuit card::suit(void)
{
return suit_;
}

inline char * card::rankText(void)
{
return (char *)cards[(int)rank_ - 1];
}

inline char * card::suitText(void)
{
return (char *)suits[(int)suit_];
}

inline void card::set_rank(cardRank r)
{
rank_ = r;
}

inline void card::set_suit(cardSuit s)
{
suit_ = s;
}

inline void card::set_card(cardSuit s, cardRank r)
{
rank_ = r;
suit_ = s;
}

inline void card::get_card(cardSuit &s, cardRank &r)
{
r = rank_;
s = suit_;
}

deck::deck(void)
{
int n = 0;

for (int s = int(Diamond); s <= int(Spade); ++s)
{
for (int c = int(Ace); c <= int(King); ++c)
{
deck::card_[n].set_rank(cardRank(c));
deck::card_[n].set_suit(cardSuit(s));
++n;
}
}
top = 0;
}

inline void deck::deal(class card &c)
{
if (top < Deck_Size)
c = deck::card_[top++];
}

inline int deck::cards_left(void)
{
return int(Deck_Size - top);
}

void deck::shuffle(void)
{
int used[Deck_Size], posn = 0;

srand((unsigned)time(NULL) | 1);
memset(used, 0, Deck_Size * sizeof(int));

for (int s = int(Diamond); s <= int(Spade); ++s)
{
for (int c = int(Ace); c <= int(King); ++c)
{
posn = (posn + rand()) % Deck_Size;
while (used[posn])
posn = ++posn % Deck_Size;
deck::card_[posn].set_rank(cardRank(c));
deck::card_[posn].set_suit(cardSuit(s));
used[posn] = -1;
}
}
top = 0;
}

#ifdef TEST

#include <iostream.h>

void showem(class deck &d);

main()
{
class deck d;

cout << "Deck initially:" << endl << endl;
showem(d);
d.shuffle();
cout << endl << "After shuffling:" << endl << endl;
showem(d);
return EXIT_SUCCESS;
}

void showem(class deck &d)
{
for (int i = 0; i <= Deck_Size; ++i)
{
class card card_;

if (0 < d.cards_left())
{
d.deal(card_);
cout << "Card #";
cout.width(2);
cout << (i + 1) << " - " <<
card_.rankText() << " of " <<
card_.suitText() << endl;
}
else  cout << "No cards left" << endl;
}
}

#endif // TEST
I hope, this helps. Alex
0

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

~Aaron
0

Commented:
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 ...
0

Author Commented:
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 )

0

Commented:
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.
0

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

Commented:
The accepted answer gives a biased shuffle even assuming a perfect rand
0

Commented:
how is it biased?

~Aaron
0

Commented:
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.
0

Author Commented:
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.
0

Author Commented:
Correction: don't mod the random number.
0

Commented:
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
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.