Shuffling a Deck of Cards , Redundancy after swapping two values

Question

I was asked to write a program(mainly a method) for shuffling a deck of cards. I wrote the following program:

public class Deck {

////////////////////////////////////////
// Data Members
////////////////////////////////////////

private Card[] cards; // array holding all 52 cards
private int cardsInDeck; // the current number of cards in the deck

public static final int DECK_SIZE = 52;

/**
 * Shuffles the deck (i.e. randomly reorders the cards in the deck). 
 */
public void shuffle() {
    int newI;
    Card temp;
    Random randIndex = new Random();

    for (int i = 0; i < cardsInDeck; i++) {

        // pick a random index between 0 and cardsInDeck - 1
        newI = randIndex.nextInt(cardsInDeck);

        // swap cards[i] and cards[newI]
        temp = cards[i];
        cards[i] = cards[newI];
        cards[newI] = temp;
    }
}

}

But there is a logical error in the above shuffle method which is as follows: Suppose I replace Card Number 4 with Card Number 42, then I'm swapping two times. I'm wondering is there any way of not doing this?

I checked one post here :Shuffling a deck of cards

But it didn't make sense to me.

Answer 1

I'm wondering is there any way of not doing this?

Absolutely. Instead of swapping one card with any other, simply swap one card with a later one.

So at any point, you're really picking which card is going to be in slot i from "all the remaining cards" which haven't been picked. It's conceptually equivalent to starting with one list of cards, and removing cards at random to place in the new shuffled collection. The fact that you're actually swapping locations while you're doing that is irrelevant, as at any point you'll be picking uniformly randomly from the remaining slots.

Read the Wikipedia article on the Fisher-Yates shuffle for more information.

(Some implementations swap from the end, so element x is swapped with a random element in the range [0, x]. That's equivalent to what I described, just mirrored. Personally I find it easier to think of the first part of the collection as being the shuffled part at any point, but that's a failing on my part rather than an inherent difference.)

Also bear in mind that if you use a List<Card>, you can use Collections.shuffle and avoid having to write the code for this at all.

Answer 2

You can compare your implementation with Collections.shuffle, that one definitely works right, this is a snippet from src

  // Shuffle array
  for (int i=size; i > 1; i--)
      swap(arr, i-1, rnd.nextInt(i));

...

   private static void swap(Object[] arr, int i, int j) {
        Object tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }