www.gibmonks.com

Main 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 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 ? '\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.