https://scratch.mit.edu/projects/188460120/
Java Coding Exercise
Change and add code as described in the comments below.
public class KnuthShuffle
{
private static int random(int i, int j)
{
double r = Math.random();
return i; // Return a random integer between i inclusive and j inclusive.
}
private static void swap(int[] a, int i, int j)
{
// Swap the values at positions i and j of a.
}
private static void tally(int[] a, int[][] t)
{
int n = a.length;
for (int i = 0; i < n; i++)
{
t[a[i]][i]++;
}
}
private static String arrayToString(String[] a, int[] ranks)
{
String s = "a:";
// Append the elements of a to s in the order defined by ranks.
return s + "\n";
}
private static String tallyToString(int[][] t)
{
String s = "";
int n = t.length;
for (int i = 0; i < n; i++)
{
s += i + ":";
// Append the elements of t to s.
s += "\n";
}
return s;
}
private static int[] toRanks(int n)
{
int[] ranks = new int[n];
for (int i = 0; i < n; i++)
{
// Set the value of ranks at position i.
}
return ranks;
}
public static int[] shuffle(String[] a)
{
int n = a.length;
int[] ranks = toRanks(n);
// Shuffle the elements of ranks.
// Use the modern version of the Fisher-Yates shuffle algorithm.
return ranks;
}
public static void main(String[] args)
{
int [] ranks = {};
int n = args.length;
int[][] t = new int[n][n];
for (int count = 0; count < 10000; count++)
{
ranks = shuffle(args);
tally(ranks, t);
}
String s = tallyToString(t);
s += arrayToString(args, ranks);
System.out.print(s);
}
}
Sample Input/Output
Command-line arguments:
when KnuthShuffle is implemented as expected
when KnuthShuffle.random() returns i
when KnuthShuffle.shuffle() has an off-by-one bug
Q & A
- In the main method the for loop executes 10,000 times; why is that?
Good question! Ten thousand is an arbitrary number, but I chose it for a couple of reasons. First, since the program is shuffling the elements in the ranks array via Math.random(), I have no way of predicting what any particular permutation or series of permutations is going to look like. (And you expect me to grade your work fairly. Right?) However, given enough iterations, one can begin to see interesting patterns. In particular, what I'm looking for are bugs in students' implementations of the shuffle method that might be difficult to spot if I only looked at one or two or even 20 permutations or "shufflings" of the values in the ranks array. Second, by executing the loop 10,000 times and thinking about what all is happening in each execution of the loop, you can begin to appreciate how quickly today's computers can perform a series of tasks, and it's helpful to have a feel for what computers are capable of doing.
10,000 is also fun number to think about.
- What exactly is the rank part of the code?
That's a good question too! Maybe I should have been more clear. Or maybe it's good for you to ponder little puzzles like this. In any event, let's start by examining the toRanks() method. Given a number n, toRanks() should return the array of values {0, 1, ..., n - 1}. For example, if n is 5, then toRanks() should return {0, 1, 2, 3, 4}. The ranks array is simply a list of indices that can be shuffled without changing the array (e.g. args) that ranks may be associated with. By shuffling the ranks array instead of shuffling args, we can leave the values of the args array in their original order and repeat and study the experiment of shuffling a sequence of values exactly one time as opposed to shuffling values and then shuffling the shuffled values and so on. This is important, because some types of bugs (bugs in the implementation of KnuthShuffle.shuffle(), in particular) are harder to detect if you repeatedly shuffle previously shuffled sequences and look at the tallies than if you repeatedly shuffle the initial sequence one time and study the results.
- When you say "append the elements of t to s", does that mean to add on to it so add the t's to s?
Yes. In tallyToString(), I want you to construct a string of characters and then return the string. See the Sample Input/Output section on this page for illustrations of exactly what the string should look like, and note how the output produced is related to the code in the main() method, where strings returned by tallyToString() and arrayToString() are concatenated and then output via System.out.print().
I could have designed methods named, say, printTally() and printArray() that simply printed the output instead of designing tallyToString() and arrayToString() the way they are; in fact, that's what I did at first. But in the process of converting the Java code I wrote to JavaScript so that I could produce buttons and programs (on this page) that you can use to check your work, I decided — due to the way I'm outputting the data via JavaScript — to build up a string of characters and and output that string once in the main() method instead of outputting portions of the string in separate methods. (I want the Java and JavaScript code to be as similar as possible.)
- How do I convert the value returned by Math.random() from a double to an integer?
One way is to explicitly cast the value to an int. For example:
int zero = (int) Math.random(); - How do I convert the value returned by Math.random() to a random integer that is between two integers?
There's more than one way, and it depends. Let's say you want to convert the value returned by Math.random() to an integer that is greater than or equal to m and less than or equal to n; m is less than n; and m and n are integers. You can multiply the value returned by Math.random() by 1 + n - m, add m, and then truncate (either using Math.floor() or by casting from double to int as described above). Alternatively, you can multiply the value returned by Math.random() by 1 + n - m, add m, subtract 0.5, and then round using Math.round(). No matter what technique you use, the range of values returned by Math.random() needs to somehow be mapped to a range of values that can be partitioned into distinct intervals of equal length that in turn map to one of the possible integers with equal probability.
- Is the return type of the swap() method really supposed to be void? I thought swap() would have been used in writing the shuffle method.
Swap does return void, and it is supposed to be used in writing the shuffle method. An interesting thing about passing arrays as arguments to methods is that instead of passing a copy of the array and its values, a copy of the address of the array is passed. Therefore, any modifications you make to the array within a method via the array's address persist after the method returns control to the code that called the method. In other words, the swap method doesn't need to return a value, because it can make changes to the array that are observable outside the scope of swap(), even without returning a value. These sorts of changes are sometimes called side-effects. This point is discussed at length in your textbook and is something you should invest some time trying to understand well and remember.
- I have a question about the method arrayToString. Your comment says:
/* Append the elements of a to s in the order defined by ranks. */
I understand that appending the elements could be done using:s += " " + a[i];
But what does it mean to append them in the order defined by ranks?Since you asked your question the way you did, I am happy to answer by saying that it means:
s += " " + a[ranks[i]];
instead of:s += " " + a[i];
It's a little easier to say in Java than in English! - When I use this page to see what the output is supposed to look like, I see that the values are in groups of four. Does our output also need to be in groups of four?
For a given set of inputs, the output should look exactly like what is shown on this page when you press the button labeled "KnuthShuffle.main(args)" and the radio button "when KnuthShuffle is implemented as expected" is checked. Note that the main method concatenates two strings and then prints the result. The first of the two strings that is joined (or "concatenated") together is the value returned by tallyToString(), and it accounts for all but the last line of output; those lines of output are showing how often a value that was originally at position i ended up in one of the other positions after shuffling. The last line of output shows what the shuffled list of strings looks like after the very last shuffling.
- I am not really sure what method to use in order to append t to s. How do I do that?
You don't have to use a method to append values to s (a variable of type String). You can use the += or the + operator to concatenate two strings and return the concatenated value. In the particular case that you refer to, you will need to write another (inner) loop, such as a for loop, to iterate through the elements of the inner arrays of the two-dimensional array t so that you can append each element of the ith array (i.e. each element of t[i]) to s.
