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;
}