www.gibmonks.com

Main Page




Previous Page
Next Page

[Page 432 (continued)]

8.11. 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.


[Page 433]

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.


[Page 434]

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

Figure 8.24. Pseudocode algorithm for card shuffling and dealing program.
(This item is displayed on page 435 in the print version)


 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).


[Page 435]

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 <iostream>
 5  using std::cout;
 6  using std::left;
 7  using std::right;
 8
 9  #include <iomanip>
10  using std::setw;
11
12  #include <cstdlib> // prototypes for rand and srand
13  using std::rand;
14  using std::srand;
15
16  #include <ctime> // 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 ? '\n' : '\t'  );         
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



[Page 437]

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.


Previous Page
Next Page