Информатика · объяснение и практика
Fisher—Yates: почему случайный обмен требует правильной границы
Перемешивание Fisher—Yates: выбор из оставшегося диапазона, равномерность перестановок и ошибка обмена со всем массивом.

В теме Методы алгоритмов: углубление · Учебная карта
В маршруте Случайность, численные оценки и целостность · 10 тем
Главная мысль
В варианте Fisher—Yates слева направо на шаге i выбирают позицию j равномерно среди ещё не закреплённых i…n−1 и меняют элементы i и j. Уже готовый префикс больше не трогают. Самообмен разрешён и необходим для полной равномерности.
Закрепляем по одной позиции
Пусть карточки имеют разные метки А, Б и В. Для первой позиции выбираем любую из трёх с равными шансами. Для второй — любую из оставшихся двух; третья определяется автоматически. Каждая конкретная перестановка получается с вероятностью (1/3)·(1/2)=1/6.
Для массива из n разных элементов рассуждение продолжается: n вариантов, затем n−1 и так далее. Произведение вероятностей равно 1/n!. Важно выбирать каждый индекс равномерно, а не брать остаток от произвольного диапазона случайных чисел, если это вносит смещение. Алгоритм и качество источника случайности проверяются отдельно.
Посмотрим на границы в собственной трассе
Возьмём список А, Б, В, Г и нумерацию с нуля. На шаге 0 выбрана позиция 2: получаем В, Б, А, Г. На шаге 1 выбрана позиция 3: В, Г, А, Б. На шаге 2 выбрана сама позиция 2: список не меняется. Осталась последняя готовая позиция.
Если запретить выбор самой i, некоторые перестановки станут невозможны. Например, для двух карточек обязательный обмен всегда меняет их местами, а исходный порядок не появляется вообще. Отсутствие видимого движения на отдельном шаге поэтому не означает сбой перемешивания.
Пример
А,Б,В,Г → В,Б,А,Г → В,Г,А,Б → В,Г,А,Б. Выборы j: 2,3,2.
На каждом шаге j лежит в оставшемся диапазоне. Префикс В, затем В,Г уже не возвращается в случайный выбор.
Почему обмен со всем массивом опасен
Популярная замена выбирает для каждого i любой j от 0 до n−1. Тогда уже закреплённые места снова меняются. Для трёх элементов существует 27 равновероятных последовательностей выбора, а перестановок — 6. Разделить 27 поровну на 6 целыми количествами невозможно: этот вариант не даёт равномерного распределения.
Это доказательство конкретной ошибки границ, а не запрет любых других методов. При повторяющихся значениях лучше мысленно дать карточкам разные номера и проверять перестановку номеров. Внешне одинаковые значения скрывают различия трасс. Для учебного теста полезнее полный перебор короткого списка, чем оценка «на глаз выглядит случайно». Дополнительно проверяют сохранение всех исходных номеров: обмен не должен создавать новые карточки или терять прежние, независимо от распределения случайных индексов.
От чтения к действию
А теперь — вы
Частые вопросы
Исходный порядок может остаться?
Да. Он является одной из допустимых перестановок; требование обязательно изменить порядок задаёт другую задачу.
Генератор с фиксированным seed портит алгоритм?
Он делает трассу воспроизводимой. Свойства генератора и цель применения нужно оценивать отдельно от правильности обменов.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Резервуарная выборка: как один слот остаётся равномерным
Резервуарная выборка одного элемента: правило замены, вероятность сохранения и разница между позицией и значением.
Открыть темуСортировка вставками: как элемент находит место в готовом префиксе
Сортировка вставками на небольшом списке: готовый префикс, сдвиги больших элементов и сохранение порядка одинаковых значений.
Открыть тему