13.6. Shuffling

For most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Random numbers we saw how to generate random numbers, but it is not obvious how to use them to shuffle a deck.

One possibility is to model the way humans shuffle, which is usually by dividing the deck in two and then reassembling the deck by choosing alternately from each deck. Since humans usually don’t shuffle perfectly, after about 7 iterations the order of the deck is pretty well randomized. But a computer program would have the annoying property of doing a perfect shuffle every time, which is not really very random. in fact, after 8 perfect shuffles, you would find the deck back in the same order you started in. For a discussion of that claim, see http://www.wiskit.com/marilyn/craig.html or do a web search with the keywords “perfect shuffle.”

A better shuffling algorithm is to traverse the deck one card at a time, and at each iteration choose two cards and swap them.

Here is an outline of how this algorithm works. To sketch the program, I am using a combination of C++ statements and English words that is sometimes called pseudocode:

for (std::size_t i = 0; i < cards.size(); i++) {
  // choose a random number between i and cards.size() - 1
  // swap the ith card and the randomly-chosen card
}

The nice thing about using pseudocode is that it often makes it clear what functions you are going to need. In this case, we need something like random_int, which chooses a random integer between the parameters low and high, and swap_cards which takes two indices and switches the cards at the indicated positions.

Note

If you are even the slightest bit unsure on how to begin coding your program, pseudocode is a great place to start!

You can probably figure out how to write random_int by looking at Random numbers, although you will have to be careful about possibly generating indices that are out of range.

You can also figure out swap_cards yourself. I will leave the remaining implementation of these functions as an exercise to the reader.

Which library should we include to create random numbers?

The random_int helper is provided. Write swap_cards in its commented section, then try using them to implement the card_deck member function shuffle_deck. If done correctly, the program should output a shuffled deck of cards. If you stuck, you can reveal the extra problems at the end for help.

Example c192_shuffling_2
 1#include <cstddef>
 2#include <random>
 3#include <iostream>
 4#include <string>
 5#include <vector>
 6#include <cstdlib>
 7
 8enum card_suit { clubs, diamonds, hearts, spades };
 9
10enum card_rank { ace=1, two, three, four, five, six, seven, eight, nine,
11ten, jack, queen, king };
12
13std::size_t random_int(std::size_t low, std::size_t high) {
14    static std::mt19937 engine(std::random_device{}());
15    return std::uniform_int_distribution<std::size_t>{low, high}(engine);
16}
17
18struct playing_card {
19    card_rank rank;
20    card_suit suit;
21    playing_card ();
22    playing_card (card_suit s, card_rank r);
23    void print () const;
24};
25
26struct card_deck {
27    std::vector<playing_card> cards;
28    card_deck ();
29    void print () const;
30    void swap_cards (std::size_t index1, std::size_t index2);
31    void shuffle_deck ();
32};
33
34void card_deck::swap_cards (std::size_t index1, std::size_t index2) {
35    // ``swap_cards`` should take two indices and switch the cards
36    // at the indicated positions. Write your implementation here.
37}
38
39void card_deck::shuffle_deck () {
40    // Follow the pseudocode from above and use ``random_int`` and
41    // ``swap_cards`` to write the ``shuffle`` member function.
42    // Write your implementation here.
43}
44
45int main() {
46    card_deck deck;
47    deck.shuffle_deck ();
48    deck.print ();
49}
random_int Help

Return a uniformly distributed index between low and high, inclusive. Assume low <= high. Include <random> and <cstddef>.

  1.     return distribution(engine);
}
  2. static std::mt19937 engine(std::random_device{}());
  3. std::size_t random_int(std::size_t low, std::size_t high) {
  4. std::uniform_int_distribution<std::size_t> distribution(low, high);
swap_cards Help

Let's write the code for the swap_cards function. We'll write swap_cards as a card_deck member function that takes two indices as parameters.

  1.  cards[index2] = temp;
}
  2. cards[index1] = cards[index2];
  3. cards[index2] = cards[index1];
  4. playing_card temp = cards[index1];
  5. void card_deck::swap_cards (std::size_t index1, std::size_t index2) {
  6. void playing_card::swap_cards (std::size_t index1, std::size_t index2) {
shuffle_deck Help

Let's write the code for the shuffle_deck function. We'll use random_int and swap_cards in our implementation of shuffle_deck.

  1.   swap_cards (i, x);
 }
}
  2. card_deck card_deck::shuffle_deck (card_deck deck) {
  3. for (std::size_t i = 0; i < cards.size(); i++) {
  4. std::size_t x = random_int (i, cards.size() - 1);
  5. std::size_t x = random_int (i, cards.size());
  6. void card_deck::shuffle_deck () {