Java's Collections.shuffle is doing what?

Question

I recently found myself needing to be sure my list wasn't in order. Hibernate was nice enough to return it in perfect order. Silly hibernate, not reading my mind.

I looked at my Java API and it tells me its shuffle method does this:

Randomly permutes the specified list using a default source of randomness.

Being the curious george that I am, I want to know what exactly this means. Is there a math course I can take to learn this? Can I see the code? Java, what are you doing to my ArrayList?!?!?

To be more specific, which math concepts are being used here?

Answer 1

Yes, you can look at the code; it basically does a Fisher-Yates shuffle. Here it is (thanks OpenJDK, and yay for open source :-P):

public static void shuffle(List<?> list, Random rnd) {
    int size = list.size();
    if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
        for (int i=size; i>1; i--)
            swap(list, i-1, rnd.nextInt(i));
    } else {
        Object arr[] = list.toArray();

        // Shuffle array
        for (int i=size; i>1; i--)
            swap(arr, i-1, rnd.nextInt(i));

        // Dump array back into list
        ListIterator it = list.listIterator();
        for (int i=0; i<arr.length; i++) {
            it.next();
            it.set(arr[i]);
        }
    }
}

The swap method:

 private static void swap(Object[] x, int a, int b) {
    Object t = x[a];
    x[a] = x[b];
    x[b] = t;
}

Answer 2

The Collections JavaDoc gives some information on the shuffle method used.

This implementation traverses the list backwards, from the last element up to the second, repeatedly swapping a randomly selected element into the "current position". Elements are randomly selected from the portion of the list that runs from the first element to the current position, inclusive.

So it starts at the end and walks the list backwards. At each element it stops and swaps the current element with a preceding element from the list. The "default source of randomness" in this case is probably a Random object created with a default seed.