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