Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Card Shuffling algorithm

Posted on 1999-10-08
12
Medium Priority
?
1,373 Views
Last Modified: 2009-03-26
Is there a standard Card Shuffling algorithm that is guaranteed to give a good shuffle?
0
Comment
Question by:aborman
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 3
  • 2
  • +4
12 Comments
 
LVL 3

Expert Comment

by:BudVVeezer
ID: 2111507
I'm interested, so I'm listening.  I know cards.dll does it...but no clue HOW.

~Aaron
0
 
LVL 1

Expert Comment

by:Aggarwal
ID: 2111601
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 Comment

by:aborman
ID: 2111609
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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 22

Expert Comment

by:cookre
ID: 2111675
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
 
LVL 84

Expert Comment

by:ozo
ID: 2112026
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
 
LVL 14

Accepted Solution

by:
AlexVirochovsky earned 800 total points
ID: 2112181
Next is cards class for shuffling:
cards.hpp
// +++Date last modified: 05-Jul-1997

/*
**  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:
// +++Date last modified: 05-Jul-1997

/*
**  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.setf(ios::left, ios::adjustfield);
                  cout << (i + 1) << " - " <<
                        card_.rankText() << " of " <<
                        card_.suitText() << endl;
            }
            else  cout << "No cards left" << endl;
      }
}

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

Expert Comment

by:ozo
ID: 2117519
The accepted answer gives a biased shuffle even assuming a perfect rand
0
 
LVL 3

Expert Comment

by:BudVVeezer
ID: 2117849
how is it biased?

~Aaron
0
 
LVL 84

Expert Comment

by:ozo
ID: 2124922
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 Comment

by:aborman
ID: 2186622
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 Comment

by:aborman
ID: 2186980
Correction: don't mod the random number.
0
 
LVL 1

Expert Comment

by:Moondancer
ID: 6821333
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

670 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question