Colecciones de Java.shuffle está haciendo qué?

Question

Recientemente me encontré necesitando estar seguro de que mi lista no estaba en orden. Hibernate fue lo suficientemente agradable como para devolverlo en perfecto orden. Tonto hibernate, no leyendo mi mente.

miré el API de Java y me dice que su método aleatorio hace esto:

permuta aleatoriamente la lista especificada usando una fuente por defecto de aleatoriedad.

Siendo el George tan curioso que soy, quiero saber exactamente qué significa. ¿Hay algún curso de matemáticas que pueda tomar para aprender esto? ¿Puedo ver el código? Java, ¿qué haces con mi ArrayList?!?!?

Para ser más específicos, ¿qué conceptos matemáticos se usan aquí?

Answer 1

Sí, puede ver el código; Básicamente hace un Fisher-Yates shuffle. Aquí es (gracias OpenJDK y saltan para :-P de código abierto):

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

El método de intercambio:

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

Answer 2

El Collections JavaDoc da alguna información sobre el método utilizado aleatoria.

Esta implementación cruza la lista hacia atrás, desde el último elemento hasta el segundo, intercambiando repetidamente un elemento seleccionado al azar en la "posición actual". Los elementos se seleccionan al azar de la parte de la lista que se extiende desde el primer elemento hasta la posición actual, inclusive.

Por lo tanto, comienza al final y recorre la lista hacia atrás. En cada elemento se detiene y cambia el elemento actual por un elemento precedente de la lista. La "fuente de aleatoriedad predeterminada" en este caso es probablemente un objeto Random creado con un valor inicial predeterminado.