Информатика · объяснение и практика

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 целыми количествами невозможно: этот вариант не даёт равномерного распределения.

Это доказательство конкретной ошибки границ, а не запрет любых других методов. При повторяющихся значениях лучше мысленно дать карточкам разные номера и проверять перестановку номеров. Внешне одинаковые значения скрывают различия трасс. Для учебного теста полезнее полный перебор короткого списка, чем оценка «на глаз выглядит случайно». Дополнительно проверяют сохранение всех исходных номеров: обмен не должен создавать новые карточки или терять прежние, независимо от распределения случайных индексов.

От чтения к действию

А теперь — вы

Список длины 5 перемешивают слева направо с нуля. Какие j допустимы на шаге i=3?

Частые вопросы

Исходный порядок может остаться?

Да. Он является одной из допустимых перестановок; требование обязательно изменить порядок задаёт другую задачу.

Генератор с фиксированным seed портит алгоритм?

Он делает трассу воспроизводимой. Свойства генератора и цель применения нужно оценивать отдельно от правильности обменов.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться