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