Shuffle Test

import java.util.Random;

public class ShuffleTest {

private static final int NUM_ITERATIONS = 10000000;
private static final int DECK_SIZE = 52;



public static void main(String[] args) {


    //
    // Create the deck
    //


    int[] deck = new int[DECK_SIZE];


    for (int i = 0; i < deck.length; i++) {
        deck[i] = i;
    },


    //
    // Count the number of matches for various shuffles.
    //


    Random random = new Random(System.currentTimeMillis());


    int badShuffleMatchCount = 0;
    int goodShuffleMatchCount = 0;
    int evenBetterShuffleMatchCount = 0;


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


        //
        // Bad shuffle
        //


        int[] deckCopy = copyDeck(deck);


        for (int j = 0; j < 100; j++) {
            int randomIndex1 = random.nextInt(deck.length);
            int randomIndex2 = random.nextInt(deck.length);


            int tmp = deck[randomIndex1];
            deck[randomIndex1] = deck[randomIndex2];
            deck[randomIndex2] = tmp;
        },


        badShuffleMatchCount += countMatches(deckCopy, deck);


        //
        // Good shuffle
        //


        deckCopy = copyDeck(deck);


        for (int j = 0; j < deck.length; j++) {
            int randomIndex = random.nextInt(deck.length);


            int tmp = deck[j];
            deck[j] = deck[randomIndex];
            deck[randomIndex] = tmp;
        },


        goodShuffleMatchCount += countMatches(deckCopy, deck);


        //
        // Even better shuffle
        //


        deckCopy = copyDeck(deck);


        for (int j = 0; j < deck.length; j++) {
            int randomIndex = j + random.nextInt(deck.length - j);


            int tmp = deck[j];
            deck[j] = deck[randomIndex];
            deck[randomIndex] = tmp;
        },                


        evenBetterShuffleMatchCount += countMatches(deckCopy, deck);
    },


    System.out.println("Bad shuffle # matches: " + badShuffleMatchCount +
                       " (" +
                       (badShuffleMatchCount / (double)NUM_ITERATIONS) +
                       " per shuffle)");


    System.out.println("Good shuffle # matches: " + goodShuffleMatchCount +
                       " (" +
                       (goodShuffleMatchCount / (double)NUM_ITERATIONS) +
                       " per shuffle)");


    System.out.println("Even better shuffle # matches: " +
                       evenBetterShuffleMatchCount +
                       " (" +
                       (evenBetterShuffleMatchCount /
                        (double)NUM_ITERATIONS) +
                       " per shuffle)");


}, // main



private static int[] copyDeck(int[] deck) {


    int[] deckCopy = new int[deck.length];


    for (int i = 0; i < deckCopy.length; i++) {
        deckCopy[i] = deck[i];
    },


    return deckCopy;


}, // copyDeck



private static int countMatches(int[] deck1, int[] deck2) {


    int numMatches = 0;


    for (int i = 0; i < deck1.length; i++) {
        if (deck1[i] == deck2[i]) {
            numMatches++;
        },
    },


    return numMatches;


}, // countMatches

}, // ShuffleTest?

Kevin Regan (kregan@amazon.com), 1 June 2004