Guess what everybody?!
I've got the solution to the Friday Free Stuff Puzzler!
Which means we've got a winner(s)!
Here's the solution... straight from the personal email accounts of Dr. Josh Bloch and Dr. Neal Gafter....
--------------------------
As usual the MMQC readers have distinguished themselves. The grand prize (a fine rolling backpack) goes to AT of Odessa, Ukraine. He posted the first solution, and it was correct, complete, and concise. As you'll recall, we asked you whether the following shuffle method was correct, in other words, produced all permutations with equal likelihood:
import java.util.Random;
public class Puzz {
private static Random rnd = new Random();
public static void shuffle(Object[] a) {
for (int i = 0; i < a.length; i++)
swap(a, i, rnd.nextInt(a.length));
}
private static void swap(Object[] a, int i, int j) {
Object tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
AT pointed out that for an array of length n, the shuffle method generates one of nn possible permutations depending on the value returned by the random number generator, but there are n! possible permutations of n objects. The problem is that nn isn't divisible by n! for any n > 2: n! is divisible by (n - 1) and and nn is not. This proves beyond the shadow of a doubt that the shuffle method does not work properly, but it gives no insight into the bias in the results that it returns. Describing the bias is, as they say, left as an exercise to the reader.
AT's fix is to swap each element of the array with a randomly selected element from the subarray starting at that element:
for (int i = 0; i < a.length; i++)
swap(a, i, i + rnd.nextInt(a.length-i));
He points out that this is easy to prove correct by induction. For the base case, the algorithm is trivially correct for an array of length zero. For the induction step, if you apply it to an array of length n, it correctly selects a random element for the zeroth position of the result and then applies the same algorithm to the remaining elements in the "subarray" consisting of the all the elements in the array except for the zeroth.
Jeff Chilton's proof of the incorrectness of the given algorithm is fuzzy (or as mathematicians like to say, "wrong"), but his proposed algorithm is almost correct, though slower and less elegant than AT's. The reason we say "almost" is that it tries to return its result by setting an input parameter:
public static void shuffle(Object[] a) {
List source = new ArrayList();
List target = new ArrayList();
for (int i = 0; i < a.length; i++) {
source.add(a[i]);
}
while (source.size() > 0) {
int x = rnd.nextInt(source.size());
target.add(source.remove(x));
}
a = target.toArray(new Object[0]);
}
}
If Jeff had actually run his method, he would have found out that it always leaves a in the same order that it was in before the method was invoked. For his effort, Jeff wins 2.718281828 pounds of stinky tofu.
Tom Hawtin's proof is also correct, though we give AT's nonconstructive proof the nod for elegance. Tom's solution, however, rocks:
import java.util.Arrays;
import java.util.Collections;
public class Puzz {
private static final Random rnd = new Random();
public static void shuffle(Object[] a) {
Collections.shuffle(Arrays.asList(a), rnd);
}
}
As some great sage (OK, it was Josh) once said, "know and use the libraries." For his effort, Tom is awarded second prize, to be determined your hostess.
Kevin performed an experiment suggesting that the given algorithm is wrong. Not quite a proof, but nice nonetheless. Click and Hack like empirical results.
Kevin claims that the algorithm doesn't work for an array of length two. Kevin is wrong. That is one of the three cases for which it does work. The others are zero and one. Had Kevin run the program for an array of length two, he would have known this. Stinky tofu for Kevin. That said, Kevin's suggested solution works fine (though it has an extraneous line in it). It is roughly equivalent to Jeff's solution without the return value gaffe.
Trevor's solution also appears to be correct, though the loop is a bit quirky, and the fact the look index is both decremented and incremented is a bit inelegant. Aaron's solution looks fine.
For those who just can't get enough, here's a program that calculates the expected value of the element at the each position when the original (broken) algorithm is run on the "identity array" (where a[i] = i). It lends some insight into the effects of the breakage.
public class BrokenShuffle {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
int[] indices = new int[n];
long[] totals = new long[n];
nestedLoop(indices, 0, totals);
double nToTheN = 1;
for (int i = 0; i < n; i++)
nToTheN *= n;
for (int i = 0; i < n; i++)
System.out.println(i + ": " + totals[i] / nToTheN);
}
static void nestedLoop(int[] indices, int ii, long[] totals) {
int n = indices.length;
if (ii == n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = i;
for (int i = 0; i < n; i++)
swap(a, i, indices[i]);
for (int i = 0; i < n; i++)
totals[i] += a[i];
} else {
for (indices[ii] = 0; indices[ii] < n; indices[ii]++)
nestedLoop(indices, ii + 1, totals);
}
}
private static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
A word to the wise: the runtime of this program is O(nn). Got CPU cycles? And for heaven's sake, don't code like my brother
------------------------
And that means we've got some business to attend to:
1. AT: You, my friend, are the grand prize winner!!! This ultra cool backpack will soon be on its way to you in the Ukraine. (!) How neat-o is that? For the record, this is the first time I've ever shipped stuff to the Ukraine. Places I've sent stuff to include South Africa, Austrailia, Singapore, Brazil, India, Saudi Arabia, all over Europe (I'm huge in German. Huge. Me and David Hasselhoff.), and other places. I don't really know, actually. I don't track it for privacy reasons. (yours)
2. Tom: Click and Hack said your solution "rocks." How sweet is that?! I got a conference bag from the Tech Days in New York for you, my friend!
3. Everybody else: (including Jeff and Kevin, because I don't have any stinkin' Tofu) you get prizes too! A pen! A really nice pen -- the heavy-in-your-hand kind.
Here's what you do: send email to me using the following formula: first.last@sun.com. firstname: mary. lastname: smaragdis. I need your mailing address. I'll use it for the singular purpose of copying it down onto an envelope/box to send you the free stuff. I won't share it with anybody. I won't use it for any other purpose whatsoever. I'll delete the mail after I've copied it down.
So the big take-aways here are:
1. It's truly unbelievable that you guys read my blog. It literally blows me away to find out who's reading this thing.
2. I am probably the only girl on the entire unwashed Internet who's got stuff in her blog that she does not understand.
3. Click and Hack rock the house.
And isn't that just a perfect way to round out a very happy Monday?
told you it was going to be happy. didn't i. told you.
:-)
mary
