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