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}