array - shuffle java

Java''s Collections.shuffle está haciendo qué?

Question

Recientemente me encontré a mí mismo 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é mi API de Java y me dice que su método aleatorio hace esto:

Cambia aleatoriamente la lista especificada utilizando una fuente predeterminada de aleatoriedad.

Siendo el George tan curioso que soy, quiero saber exactamente qué significa esto. ¿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ífico, ¿qué conceptos matemáticos se usan aquí?

Answer 1

Sí, puedes mirar el código; básicamente hace una mezcla de Fisher-Yates . Aquí está (gracias OpenJDK, y yay por código abierto :-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]);
}
}
}

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

The Collections JavaDoc proporciona información sobre el método de mezcla utilizado.

Esta implementación atraviesa 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.

Entonces comienza al final y recorre la lista al revés. En cada elemento se detiene y cambia el elemento actual por un elemento precedente de la lista. La "fuente predeterminada de aleatoriedad" en este caso es probablemente un objeto Random creado con un valor inicial predeterminado.