Математика справедливого перемешивания

Перемешивание ставит точный математический вопрос: имея n различных объектов, получить одну из n! возможных расстановок, каждую с одинаковой вероятностью. Для 52 целых чисел это означает 8.07 × 10⁶⁷ перестановок. Последовательность выше была выбрана из этого пространства с равномерной вероятностью, сгенерирована полностью в вашем браузере с использованием алгоритма Фишера — Йейтса и Web Cryptography API.

Фишер — Йейтс: эталонный алгоритм

Рональд Фишер и Фрэнк Йейтс описали оригинальный метод перемешивания в своей книге 1938 года Statistical Tables for Biological, Agricultural and Medical Research. Дональд Кнут позже доработал его для компьютерной реализации в The Art of Computer Programming (1969). Современная версия проходит по массиву в обратном порядке. На каждой позиции выбирается случайный элемент из оставшейся неперемешанной части, и элементы меняются местами. Один проход по данным даёт идеальное равномерное перемешивание за время O(n) с использованием O(1) дополнительной памяти.

Доказательство корректности показывает, что после обработки позиции k каждая из k! возможных подрасстановок первых k элементов равновероятна. По индукции конечный результат покрывает все n! перестановок с одинаковой вероятностью. Распространённая ошибка реализации — «наивное перемешивание» — на каждом шаге выбирает элемент из всего массива, а не из необработанной части. Это порождает nⁿ последовательностей обменов, отображаемых на n! перестановок. Поскольку nⁿ, как правило, не делится на n!, некоторые перестановки становятся более вероятными. Алгоритм Фишера — Йейтса полностью исключает эту проблему.

Ошеломляющий масштаб перестановок

Факториальный рост опережает любую другую распространённую математическую функцию. Десять элементов дают 3 628 800 расположений. Двадцать элементов — более 2,4 квинтиллиона. Стандартная колода из 52 карт порождает примерно 8,07 \xC3\x97 10\xE2\x81\xB6\xE2\x81\xB7 возможных расстановок. Это число превышает предполагаемое количество атомов в наблюдаемой Вселенной.

Представьте: если бы каждый атом во Вселенной перемешивал колоду раз в наносекунду и делал это с момента Большого взрыва 13,8 миллиарда лет назад, общее число выполненных перемешиваний всё равно составило бы исчезающе малую долю от 52!. Каждое перемешивание, которое вы выполняете на этой странице, почти наверняка создаёт расположение, которое никогда раньше не существовало и никогда больше не повторится.

Неподвижные точки: парадокс беспорядков

Неподвижная точка — это число, которое после перемешивания остаётся на своей исходной позиции. Обратите внимание на круги с золотой обводкой выше — это ваши неподвижные точки. Ожидаемое количество неподвижных точек равно ровно 1 независимо от числа перемешиваемых элементов. Десять элементов — одна ожидаемая неподвижная точка. Десять тысяч элементов — всё равно одна.

Вероятность того, что конкретный элемент останется на месте, равна 1/n. Суммируя по n элементам, получаем математическое ожидание, равное 1. Этот результат, связанный с математическим понятием беспорядков, изучавшихся Леонардом Эйлером, означает, что примерно 36,8% всех перемешиваний не имеют неподвижных точек, 36,8% имеют ровно одну, 18,4% — ровно две, а далее вероятности быстро убывают.

Теорема о семи перемешиваниях

Перси Диаконис и Дэйв Байер доказали в 1992 году, что стандартное рифл-перемешивание колоды из 52 карт требует ровно семи итераций для достижения достаточной рандомизации. Цифровое перемешивание по алгоритму Фишера — Йейтса за один вычислительный проход достигает того, что семь физических рифл-перемешиваний лишь приближают: идеальную равномерную рандомизацию.

В учебном классе

Попросите каждого ученика открыть /sequence/1/10 и перемешать один раз. Затем спросите: получили ли двое учеников одинаковый порядок? При 3 628 800 возможных расположений совпадение крайне маловероятно. Для демонстрации на проекторе откройте /sequence/1/52 и перемешивайте многократно. Яркие кольца каждый раз рассыпаются в новые узоры, делая случайность наглядной. Инструмент не требует регистрации, не устанавливает cookie и не хранит данные учеников.