Case Study: Card Shuffling and Dealing Simulation

Case Study Card Shuffling and Dealing Simulation

This section uses random-number generation to develop a card shuffling and dealing simulation program. This program can then be used as a basis for implementing programs that play specific card games. To reveal some subtle performance problems, we have intentionally used suboptimal shuffling and dealing algorithms. In the exercises, we develop more efficient algorithms.

Using the top-down, stepwise-refinement approach, we develop a program that will shuffle a deck of 52 playing cards and then deal each of the 52 cards. The top-down approach is particularly useful in attacking larger, more complex problems than we have seen in the early chapters.

We use a 4-by-13 two-dimensional array deck to represent the deck of playing cards (Fig. 8.23). The rows correspond to the suitsrow 0 corresponds to hearts, row 1 to diamonds, row 2 to clubs and row 3 to spades. The columns correspond to the face values of the cardscolumns 0 through 9 correspond to faces ace through 10, respectively, and columns 10 through 12 correspond to jack, queen and king, respectively. We shall load the string array suit with character strings representing the four suits (as in Fig. 8.22) and the string array face with character strings representing the 13 face values.

---

Figure 8.23. Two-dimensional array representation of a deck of cards.

This simulated deck of cards may be shuffled as follows. First the array deck is initialized to zeros. Then, a row (03) and a column (012) are each chosen at random. The number 1 is inserted in array element deck[ row ][ column ] to indicate that this card is going to be the first one dealt from the shuffled deck. This process continues with the numbers 2, 3, ..., 52 being randomly inserted in the deck array to indicate which cards are to be placed second, third, ..., and 52nd in the shuffled deck. As the deck array begins to fill with card numbers, it is possible that a card will be selected twice (i.e., deck[ row ][ column ] will be nonzero when it is selected). This selection is simply ignored, and other rows and columns are repeatedly chosen at random until an unselected card is found. Eventually, the numbers 1 through 52 will occupy the 52 slots of the deck array. At this point, the deck of cards is fully shuffled.

This shuffling algorithm could execute for an indefinitely long period if cards that have already been shuffled are repeatedly selected at random. This phenomenon is known as indefinite postponement (also called starvation). In the exercises, we discuss a better shuffling algorithm that eliminates the possibility of indefinite postponement.

Performance Tip 8.3

Sometimes algorithms that emerge in a "natural" way can contain subtle performance problems such as indefinite postponement. Seek algorithms that avoid indefinite postponement.

To deal the first card, we search the array for the element deck[ row ][ column ] that matches 1. This is accomplished with a nested for statement that varies row from 0 to 3 and column from 0 to 12. What card does that slot of the array correspond to? The suit array has been preloaded with the four suits, so to get the suit, we print the character string suit[ row ]. Similarly, to get the face value of the card, we print the character string face[ column ]. We also print the character string " of ". Printing this information in the proper order enables us to print each card in the form "King of Clubs", "Ace of Diamonds" and so on.

---

Let us proceed with the top-down, stepwise-refinement process. The top is simply

Shuffle and deal 52 cards

Our first refinement yields

Initialize the suit array
Initialize the face array
Initialize the deck array
Shuffle the deck
Deal 52 cards

"Shuffle the deck" may be expanded as follows:

For each of the 52 cards
      Place card number in randomly selected unoccupied slot of deck

"Deal 52 cards" may be expanded as follows:

For each of the 52 cards
      Find card number in deck array and print face and suit of card

Incorporating these expansions yields our complete second refinement:

Initialize the suit array
Initialize the face array
Initialize the deck array

For each of the 52 cards
      Place card number in randomly selected unoccupied slot of deck

For each of the 52 cards
      Find card number in deck array and print face and suit of card

"Place card number in randomly selected unoccupied slot of deck" may be expanded as follows:

Choose slot of deck randomly

While chosen slot of deck has been previously chosen
      Choose slot of deck randomly

Place card number in chosen slot of deck

"Find card number in deck array and print face and suit of card" may be expanded as follows:

For each slot of the deck array
      If slot contains card number
             Print the face and suit of the card

Incorporating these expansions yields our third refinement (Fig. 8.24):

 1  Initialize the suit array
 2  Initialize the face array
 3  Initialize the deck array
 4
 5  For each of the 52 cards
 6        Choose slot of deck randomly
 7
 8        While slot of deck has been previously chosen
 9            Choose slot of deck randomly
10
11        Place card number in chosen slot of deck
12
13  For each of the 52 cards
14        For each slot of deck array
15            If slot contains desired card number
16                 Print the face and suit of the card

This completes the refinement process. Figures 8.258.27 contain the card shuffling and dealing program and a sample execution. Lines 6167 of function deal (Fig. 8.26) implement lines 12 of Fig. 8.24. The constructor (lines 2235 of Fig. 8.26) implements lines 13 of Fig. 8.24. Function shuffle (lines 3855 of Fig. 8.26) implements lines 511 of Fig. 8.24. Function deal (lines 5888 of Fig. 8.26) implements lines 1316 of Fig. 8.24. Note the output formatting used in function deal (lines 8183 of Fig. 8.26).

---

Figure 8.25. DeckOfCards header file.

 1 // Fig. 8.25: DeckOfCards.h
 2 // Definition of class DeckOfCards that
 3 // represents a deck of playing cards.
 4
 5 // DeckOfCards class definition
 6 class DeckOfCards
 7 {
 8 public:
 9 DeckOfCards(); // constructor initializes deck
10 void shuffle(); // shuffles cards in deck
11 void deal(); // deals cards in deck
12 private:
13 int deck[ 4 ][ 13 ]; // represents deck of cards
14 }; // end class DeckOfCards

Figure 8.26. Definitions of member functions for shuffling and dealing.

(This item is displayed on pages 435 - 437 in the print version)

 1 // Fig. 8.26: DeckOfCards.cpp
 2 // Member-function definitions for class DeckOfCards that simulates
 3 // the shuffling and dealing of a deck of playing cards.
 4 #include 
 5 using std::cout;
 6 using std::left;
 7 using std::right;
 8
 9 #include 
10 using std::setw;
11
12 #include  // prototypes for rand and srand
13 using std::rand;
14 using std::srand;
15
16 #include  // prototype for time
17 using std::time;
18
19 #include "DeckOfCards.h" // DeckOfCards class definition
20
21 // DeckOfCards default constructor initializes deck
22 DeckOfCards::DeckOfCards()
23 {
24 // loop through rows of deck
25 for ( int row = 0; row <= 3; row++ )
26 {
27 // loop through columns of deck for current row
28 for ( int column = 0; column <= 12; column++ )
29 {
30 deck[ row ][ column ] = 0; // initialize slot of deck to 0
31 } // end inner for
32 } // end outer for
33
34 srand( time( 0 ) ); // seed random number generator
35 } // end DeckOfCards default constructor
36
37 // shuffle cards in deck
38 void DeckOfCards::shuffle()
39 {
40 int row; // represents suit value of card
41 int column; // represents face value of card
42
43 // for each of the 52 cards, choose a slot of the deck randomly
44 for ( int card = 1; card <= 52; card++ )
45 {
46 do // choose a new random location until unoccupied slot is found
47 {
48 row = rand() % 4; // randomly select the row
49 column = rand() % 13; // randomly select the column
50 } while( deck[ row ][ column ] != 0 ); // end do...while
51
52 // place card number in chosen slot of deck
53 deck[ row ][ column ] = card;
54 } // end for
55 } // end function shuffle
56
57 // deal cards in deck
58 void DeckOfCards::deal()
59 {
60 // initialize suit array 
61 static const char *suit[ 4 ] = 
62  { "Hearts", "Diamonds", "Clubs", "Spades" };
63
64 // initialize face array 
65 static const char *face[ 13 ] = 
66  { "Ace", "Deuce", "Three", "Four", "Five", "Six", "Seven",
67  "Eight", "Nine", "Ten", "Jack", "Queen", "King" }; 
68
69 // for each of the 52 cards
70 for ( int card = 1; card <= 52; card++ )
71 {
72 // loop through rows of deck
73 for ( int row = 0; row <= 3; row++ )
74 {
75 // loop through columns of deck for current row
76 for ( int column = 0; column <= 12; column++ )
77 {
78 // if slot contains current card, display card
79 if ( deck[ row ][ column ] == card )
80 {
81 cout << setw( 5 ) << right << face[ column ] 
82  << " of " << setw( 8 ) << left << suit[ row ]
83  << ( card % 2 == 0 ? '
' : '	' ); 
84 } // end if
85 } // end innermost for
86 } // end inner for
87 } // end outer for
88 } // end function deal

Figure 8.27. Card shuffling and dealing program.

(This item is displayed on pages 437 - 438 in the print version)

 1 // Fig. 8.27: fig08_27.cpp
 2 // Card shuffling and dealing program.
 3 #include "DeckOfCards.h" // DeckOfCards class definition
 4
 5 int main()
 6 {
 7 DeckOfCards deckOfCards; // create DeckOfCards object
 8
 9 deckOfCards.shuffle(); // shuffle the cards in the deck
10 deckOfCards.deal(); // deal the cards in the deck
11 return 0; // indicates successful termination
12 } // end main

 

 Nine of Spades Seven of Clubs
 Five of Spades Eight of Clubs
 Queen of Diamonds Three of Hearts
 Jack of Spades Five of Diamonds
 Jack of Diamonds Three of Diamonds
 Three of Clubs Six of Clubs
 Ten of Clubs Nine of Diamonds
 Ace of Hearts Queen of Hearts
 Seven of Spades Deuce of Spades
 Six of Hearts Deuce of Clubs
 Ace of Clubs Deuce of Diamonds
 Nine of Hearts Seven of Diamonds
 Six of Spades Eight of Diamonds
 Ten of Spades King of Hearts
 Four of Clubs Ace of Spades
 Ten of Hearts Four of Spades
 Eight of Hearts Eight of Spades
 Jack of Hearts Ten of Diamonds
 Four of Diamonds King of Diamonds
 Seven of Hearts King of Spades
 Queen of Spades Four of Hearts
 Nine of Clubs Six of Diamonds
 Deuce of Hearts Jack of Clubs
 King of Clubs Three of Spades
 Queen of Clubs Five of Clubs
 Five of Hearts Ace of Diamonds

 

---

The output statement outputs the face right justified in a field of five characters and outputs the suit left justified in a field of eight characters (Fig. 8.27). The output is printed in two-column formatif the card being output is in the first column, a tab is output after the card to move to the second column (line 83); otherwise, a newline is output.

There is also a weakness in the dealing algorithm. Once a match is found, even if it is found on the first try, the two inner for statements continue searching the remaining elements of deck for a match. In the exercises, we correct this deficiency.