Java Collections.shuffle sta facendo cosa?

Question

Di recente ho ritrovato a dover essere sicuro che il mio elenco non era in ordine. Hibernate era abbastanza bello per restituirlo in perfetto ordine. hibernate Sciocco, non leggere la mia mente.

Ho guardato il mio API Java e mi dice il suo metodo casuale fa questo:

permuta casualmente l'elenco specificato utilizzando una sorgente di default di casualità.

Essendo il George curioso che io sono, io voglio sapere che cosa esattamente questo significa. C'è un corso di matematica posso prendere per imparare questo? Posso vedere il codice? Java, cosa stai facendo al mio ArrayList?!?!?

Per essere più precisi, che concetti matematici vengono utilizzati qui?

Answer 1

Sì, si può guardare il codice; lo fa fondamentalmente un Fisher-Yates mischiare . Qui è (grazie OpenJDK, e Yay per :-P open source):

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

Il metodo di swap:

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

Answer 2

Il Collezioni JavaDoc fornisce alcune informazioni sul metodo casuale utilizzato.

  

Questa implementazione attraversa l'elenco all'indietro, dall'ultimo elemento fino alla seconda, ripetutamente scambiando un elemento casuale nella "posizione corrente". Gli elementi vengono scelti a caso dalla porzione della lista che va dal primo elemento nella posizione corrente, incluso.

Così inizia alla fine e se ne va la lista all'indietro. Ad ogni elemento si ferma e scambia l'elemento corrente con un elemento precedente dall'elenco. La "fonte di default di casualità" in questo caso è probabilmente un casuale oggetto creato con un seme di default.