001// Exercise 1.1.36
002package algs11;
003import stdlib.*;
004
005/*
006
0071.1.36 Empirical shuffle check.
008Run computational experiments to check that our shuffling code on page 32 works as advertised.
009Write a program ShuffleTest that takes commandline arguments M and N, does N shuffles of an
010array of size M that is initialized with a[i] = i before each shuffle, and prints an M-by-M table
011such that row i gives the number of times i wound up in position j for all j. All entries in the
012array should be close to N/M.
013
014Suppose we start with N=3 and run the shuffling test four times,
015resulting in the arrays:
016
017  [2, 0, 1]
018  [2, 1, 0]
019  [2, 0, 1]
020  [2, 0, 1]
021
022(This is not very likely, but it is possible)
023Then the resulting count array would be:
024
025  0: 0 3 1
026  1: 0 1 3
027  2: 4 0 0
028
029If we normalize by dividing by the number of times we ran the test,
030then we get
031
032  0: 0.000 0.750 0.250
033  1: 0.000 0.250 0.750
034  2: 1.000 0.000 0.000
035
036That is:
037element "2" was always in the first position;
038element "0" was 75/25 between second and third position;
039and likewise element "1".
040
041You could compute the standard deviation for each of these, which
042would be highest for "2".
043
044--------------------------------------------------------------------------------
045Here is a more detailed example
046
047initially: counts = {
048  {0,0,0},  // position of element 0 in shuffled array
049  {0,0,0},  // position of element 1 in shuffled array
050  {0,0,0} } // position of element 2 in shuffled array
051
052Iteration 1: test=0
053a. initialize array; a={0,1,2}
054b. shuffle array; a={1,0,2}
055c. increment counts = {
056  {0,1,0},
057  {1,0,0},
058  {0,0,1} }
059
060Iteration 2: test=1
061a. initialize array; a={0,1,2}
062b. shuffle array; a={0,2,1}
063c. increment counts = {
064  {1,1,0},
065  {1,0,1},
066  {0,1,1} }
067
068Iteration 2: test=2
069a. initialize array; a={0,1,2}
070b. shuffle array; a={0,1,2}
071c. increment counts = {
072  {2,1,0},
073  {1,1,1},
074  {0,1,2} }
075
076 */
077
078public class MyShuffleTest {
079        public static void main (String[] args) {
080                args = new String[] { "3", "40000" };
081
082                int N = Integer.parseInt (args[0]); // size of the array to shuffle
083                int numTests = Integer.parseInt (args[1]); // number of times to shuffle
084
085                if (N > Byte.MAX_VALUE) throw new RuntimeException ();
086
087                byte[] a = new byte[N]; // the array
088                double[][] counts = new double[N][N]; // a place to put the results
089
090                for (int test = 0; test < numTests; test++) {
091                        for (byte b = 0; b < a.length; b++)
092                                a[b] = b;
093                        shuffle (a);
094                        if (numTests < 10) StdOut.println (java.util.Arrays.toString (a)); // for debugging: print the shuffled array
095                        incrementCounts (counts, a);
096                }
097                printCounts (counts, numTests);
098        }
099
100        private static void swap (byte[] a, int i, int j) {
101                byte temp = a[i];
102                a[i] = a[j];
103                a[j] = temp;
104        }
105        private static void shuffle (byte[] a) {
106                int N = a.length;
107                for (int i = 0; i < N; i++)
108                        swap (a, i, i + StdRandom.uniform (N - i));
109        }
110        private static void incrementCounts (double[][] counts, byte[] a) {
111                // count[b][i] is the number of times that byte b is placed in position i
112                // TODO
113        }
114        // This function destroys the counts matrix
115        private static void printCounts (double[][] counts, int numTests) {
116                // TODO
117        }
118}