Java Collections.shuffle делает что?

Недавно мне было нужно убедиться, что мой список не в порядке. Hibernate был достаточно хорош, чтобы вернуть его в идеальном порядке. Глупый спящий режим, не читающий мой разум.

Я посмотрел на свой Java API, и он говорит, что его метод тасования делает это:

Случайно переставляет указанный список с использованием источника случайности по умолчанию.

Будучи любопытным джорджем, которым я являюсь, я хочу знать, что именно это означает. Есть ли математический курс, который я могу взять, чтобы узнать это? Могу ли я увидеть код? Java, что вы делаете с моим ArrayList?!?!?

Более конкретно, какие математические понятия используются здесь?

Ответы

Ответ 1

Да, вы можете посмотреть на код; он в основном выполняет Fisher-Yates shuffle. Здесь (спасибо OpenJDK и yay для 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]);
        }
    }
}

Метод подкачки:

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

Ответ 2

Collections JavaDoc предоставляет некоторую информацию о используемом методе тасования.

Эта реализация перемещает список назад, от последнего элемента до второго, многократно меняя случайно выбранный элемент в "текущую позицию". Элементы выбираются случайным образом из части списка, которая выполняется от первого элемента до текущей позиции включительно.

Итак, он начинается в конце и идет по списку назад. На каждом элементе он останавливается и свопит текущий элемент с предыдущим элементом из списка. "По умолчанию источник случайности" в этом случае, вероятно, является Random, созданным с использованием семени по умолчанию.