The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.


Shuffling

In the previous chapter, we worked with an array of objects, but I also mentioned that it is possible to have an object that contains an array as an instance variable. In this chapter I am going to create a new object, called a Deck, that contains an array of Cards as an instance variable.

The class definition looks like this

class Deck {
  Card[] cards;

  public Deck (int n) {
    cards = new Card[n];
  }
}

The name of the instance variable is cards to help distinguish the Deck object from the array of Cards that it contains. Here is a state diagram showing what a Deck object looks like with no cards allocated:

As usual, the constructor initializes the instance variable, but in this case it uses the new command to create the array of cards. It doesn't create any cards to go in it, though. For that we could write another constructor that creates a standard 52-card deck and populates it with Card objects:

  public Deck () {
    cards = new Card[52];
    int index = 0;
    for (int suit = 0; suit <= 3; suit++) {
      for (int rank = 1; rank <= 13; rank++) {
        cards[index] = new Card (suit, rank);
        index++;
      }
    }
  }

Notice how similar this method is to buildDeck, except that we had to change the syntax to make it a constructor. To invoke it, we use the new command:

    Deck deck = new Deck ();

Now that we have a Deck class, it makes sense to put all the methods that pertain to Decks in the Deck class definition. Looking at the methods we have written so far, one obvious candidate is printDeck (Section 11.7). Here's how it looks, rewritten to work with a Deck object:

  public static void printDeck (Deck deck) {
    for (int i=0; i<deck.cards.length; i++) {
      Card.printCard (deck.cards[i]);
    }
  }

The most obvious thing we have to change is the type of the parameter, from Card[] to Deck. The second change is that we can no longer use deck.length to get the length of the array, because deck is a Deck object now, not an array. It contains an array, but it is not, itself, an array. Therefore, we have to write deck.cards.length to extract the array from the Deck object and get the length of the array.

For the same reason, we have to use deck.cards[i] to access an element of the array, rather than just deck[i]. The last change is that the invocation of printCard has to say explicitly that printCard is defined in the Card class.

For some of the other methods, it is not obvious whether they should be included in the Card class or the Deck class. For example, findCard takes a Card and a Deck as arguments; you could reasonably put it in either class. As an exercise, move findCard into the Deck class and rewrite it so that the first parameter is a Deck object rather than an array of Cards.

For most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Section 10.6 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 Java statements and English words that is sometimes called pseudocode:

    for (int i=0; i<deck.cards.length; i++) {
      // choose a random number between i and deck.cards.length
      // swap the ith card and the randomly-chosen card
    }

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

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

You can also figure out swapCards yourself. The only tricky thing is to decide whether to swap just the references to the cards or the contents of the cards. Does it matter which one you choose? Which is faster?

I will leave the remaining implementation of these methods as an exercise to the reader.



Last Update: 2011-01-24