Java Coleções.shuffle está fazendo o que?

Question

Eu recentemente me vi precisando ser certeza de que minha lista não estava em ordem.Hibernate foi bom o suficiente para devolvê-lo em perfeita ordem.Bobo de hibernação, não lendo a minha mente.

Eu olhei para o meu API Java e ele me diz que sua shuffle método faz isso:

Aleatoriamente permutes a lista especificada usando uma fonte padrão de aleatoriedade.

Sendo o curioso george que eu sou, eu quero saber o que exatamente isso significa.Existe uma matemática é claro que eu posso tomar para aprender isso?Posso ver o código?De Java, o que você está fazendo para o meu ArrayList?!?!?

Para ser mais específico, quais conceitos matemáticos que estão sendo usados aqui?

Answer 1

Sim, você pode olhar o código;ele basicamente faz um Fisher-Yates shuffle.Aqui é (graças OpenJDK, e hei de código-fonte aberto :-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]);
        }
    }
}

O permuta método:

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

Answer 2

O Coleções JavaDoc dá algumas informações sobre o shuffle método utilizado.

Esta implementação percorre a lista de trás para frente, a partir do último elemento do segundo, repetidamente, trocando aleatoriamente um elemento selecionado para a "posição atual".Os elementos são selecionados aleatoriamente a partir da porção da lista que corre a partir do primeiro elemento para a posição atual, inclusive.

Assim, começa no final e percorre a lista de trás para frente.Em cada elemento, ele pára e troca o elemento atual com o elemento anterior da lista.O "padrão de fonte de aleatoriedade", neste caso, é, provavelmente, um Aleatória objeto criado com um padrão de sementes.