Перемешивание Фишера–Йетса: почему наивный shuffle смещён и как сделать честно
Алгоритм Фишера–Йетса простыми словами: почему наивный shuffle и sort со случайным компаратором дают смещение, доказательство равномерности, задача Shuffle an Array и выборка k элементов.
Коротко
| Вопрос | Ответ |
|---|---|
| Задача | Переставить элементы массива так, чтобы каждая из перестановок выпадала с вероятностью |
| Алгоритм | Идём с конца: на шаге меняем a[i] со случайным a[j], где включительно |
| Сложность | времени, дополнительной памяти, ровно случайных чисел |
| Частая ошибка | Брать из всего массива. Получается исходов на перестановок, и на не делится |
| Задачи | LeetCode 384 Shuffle an Array, случайная выборка элементов, тасовка колоды, A/B-распределение |
Перемешать массив — задача на пять строк. Ошибиться в ней можно одним символом, и программа продолжит «работать»: массив выглядит перемешанным, тесты проходят. Поэтому на собеседовании спрашивают не только код, но и то, почему он даёт равномерное распределение.
Что значит «честно перемешать»
У массива из различных элементов перестановок. Честное перемешивание выдаёт каждую с вероятностью . Слабее, но полезно для проверки: каждый элемент оказывается на каждой позиции с вероятностью .
Второе следует из первого, но не наоборот. Пример: циклический сдвиг массива на случайное число позиций от до . Каждый элемент попадает на каждую позицию с вероятностью , но получается всего перестановок из . Поэтому проверка «по позициям» — необходимая, но не достаточная.
Наивный shuffle и где он ломается
Самая естественная попытка: пройти по массиву и поменять каждый элемент со случайным элементом из всего массива.
import random def naive_shuffle(a): n = len(a) for i in range(n): j = random.randint(0, n - 1) # ошибка: всегда весь массив a[i], a[j] = a[j], a[i] return a
Код выглядит симметрично и даже разумно. Но давайте посчитаем точно, без случайности: переберём все варианты выбора j для массива из трёх элементов.
from collections import Counter from itertools import product def naive_exact(n): c = Counter() for js in product(range(n), repeat=n): # все n^n вариантов выбора j a = list(range(n)) for i, j in enumerate(js): a[i], a[j] = a[j], a[i] c[tuple(a)] += 1 return c print(sorted(naive_exact(3).items())) # [((0, 1, 2), 4), ((0, 2, 1), 5), ((1, 0, 2), 5), # ((1, 2, 0), 5), ((2, 0, 1), 4), ((2, 1, 0), 4)]
Всего равновероятных путей, а перестановок 6. Три перестановки получаются 5 раз, три — 4 раза. Вероятности и вместо .
Аргумент через делимость
Перебор не нужен, чтобы доказать, что наивный алгоритм неравномерен. Каждый из путей выбора равновероятен. Если бы все перестановок получались одинаково часто, то делилось бы на . Но при число делит и не делит : у и нет общих делителей, кроме единицы. Значит, равномерности быть не может.
Это хороший ответ на вопрос интервьюера «а что не так с этим кодом?». Он короткий, строгий и не требует считать вероятности.
С ростом перекос не исчезает. Для из путей одна перестановка получается 8 раз, другая — 15. Разница почти вдвое.
Алгоритм Фишера–Йетса
Рональд Фишер и Фрэнк Йетс описали метод в 1938 году для ручной работы с таблицами случайных чисел: вычёркивали элементы из списка по одному. Компьютерную версию на месте, за , опубликовал Ричард Дурстенфельд в 1964 году. Дональд Кнут привёл её во втором томе «Искусства программирования», поэтому алгоритм ещё называют тасованием Кнута.
Идея: массив делится на две части. Справа — уже готовый случайный «хвост», слева — элементы, которые ещё не размещены. На каждом шаге выбираем случайный элемент из левой части и ставим его на последнее свободное место.
import random def fisher_yates(a): for i in range(len(a) - 1, 0, -1): j = random.randint(0, i) # включительно: j может совпасть с i a[i], a[j] = a[j], a[i] return a
Отличие от наивной версии — одно: j выбирается из [0, i], а не из [0, n - 1]. Элемент, попавший в хвост, больше не трогается.
Та же функция на JavaScript:
function shuffle(arr) { for (let i = arr.length - 1; i > 0; i--) { const j = Math.floor(Math.random() * (i + 1)) // 0 <= j <= i ;[arr[i], arr[j]] = [arr[j], arr[i]] } return arr }
Стандартные библиотеки делают то же самое. random.shuffle в Python — это в точности цикл выше: for i in reversed(range(1, len(x))) и j = randbelow(i + 1). Collections.shuffle в Java тоже реализует Фишера–Йетса. На собеседовании библиотечный вызов обычно запрещают, но упомянуть его стоит.
Пример по шагам
Массив [A, B, C, D], .
| Шаг | Диапазон | Выпало | Массив после обмена | Готовый хвост |
|---|---|---|---|---|
| 1 | [A, D, C, B] | B | ||
| 2 | [A, D, C, B] | C, B | ||
| 0 | [D, A, C, B] | A, C, B |
На шаге выпало : элемент остался на месте. Это нормальный исход, и он обязан быть возможен. Иначе алгоритм не сможет выдать перестановки, где элемент стоит на своём месте.
Доказательство равномерности
Через подсчёт путей
На шаге (от до ) у есть вариант. Всего путей
Все пути равновероятны. Осталось показать, что разные пути дают разные перестановки. Посмотрим на результат: элемент на позиции однозначно говорит, какой выпал на первом шаге, потому что эта позиция больше не меняется. Дальше то же рассуждение для позиции и так далее. Значит, отображение «путь → перестановка» взаимно однозначно. путей переходят в различных перестановок, каждая получается ровно одним путём, то есть с вероятностью .
Это можно проверить перебором, как мы делали для наивной версии:
def fy_exact(n): c = Counter() ranges = [range(i + 1) for i in range(n - 1, 0, -1)] for js in product(*ranges): a = list(range(n)) for i, j in zip(range(n - 1, 0, -1), js): a[i], a[j] = a[j], a[i] c[tuple(a)] += 1 return c c = fy_exact(5) print(len(c), set(c.values())) # 120 {1}: все 5! перестановок, каждая ровно один раз
Через вероятность для одного элемента
Иногда интервьюер просит другое рассуждение: «какова вероятность, что элемент окажется на позиции ?».
Чтобы попал на позицию , нужно, чтобы на шагах его не выбрали, а на шаге — выбрали. На шаге кандидатов , и среди них, пока его не выбрали. Перемножаем:
Произведение телескопическое: каждый числитель сокращается со знаменателем следующей дроби. Остаётся для любых и .
Если эта цепочка кажется знакомой, она действительно та же, что в доказательстве резервуарной выборки. Ниже разберём, почему это не совпадение.
Задача Shuffle an Array (LeetCode 384)
Нужно реализовать класс: конструктор принимает массив, shuffle() возвращает случайную перестановку, reset() — исходный массив. Все перестановки должны быть равновероятны.
import random class Solution: def __init__(self, nums): self.original = nums[:] # копия: вызывающий код может менять свой список self.nums = nums[:] def reset(self): self.nums = self.original[:] return self.nums def shuffle(self): a = self.nums for i in range(len(a) - 1, 0, -1): j = random.randint(0, i) a[i], a[j] = a[j], a[i] return a random.seed(2) s = Solution([1, 2, 3]) print(s.shuffle()) # [2, 3, 1] print(s.reset()) # [1, 2, 3] print(s.shuffle()) # [3, 2, 1]
shuffle и reset работают за , память — на копию оригинала.
Что здесь проверяют на собеседовании:
- Копию в конструкторе. Если сохранить ссылку
self.original = nums, первый жеshuffleиспортит «оригинал», иresetвернёт перемешанный массив. - Копию в
reset. Еслиresetвернёт самself.original, а потомshuffleначнёт его менять, оригинал снова испорчен. - Можно ли перемешивать текущий массив, а не оригинал. Можно: перестановка случайной перестановки, перемешанной честно, — тоже равномерна. Независимо от того, с чего начинать, Фишер–Йетс выдаёт каждую перестановку с вероятностью .
Перемешивание сортировкой
Ещё одна популярная ошибка, особенно в JavaScript:
arr.sort(() => Math.random() - 0.5)
Компаратор возвращает случайный знак, и кажется, что сортировка «перемешает» массив. Запустим 600 000 раз на [1, 2, 3] в Node.js 22:
// Фишер–Йетс: 123: 99788, 132: 100274, 213: 99992, 231: 100256, 312: 99411, 321: 100279 // sort со случайным компаратором: // 123: 225257, 132: 37493, 213: 75271, 231: 37302, 312: 37419, 321: 187258
Исходный порядок выпадает в 6 раз чаще, чем 132. Для массива из 10 элементов первый элемент в 19,6% случаев остаётся на месте, а на пятой позиции оказывается в 6,8% случаев — при честных 10%.
Почему так:
- Компаратор противоречив. Сортировка рассчитывает, что если и , то . Случайный компаратор это нарушает, и результат зависит от того, какие сравнения делает конкретный алгоритм сортировки. Цифры будут разными в разных движках и версиях.
- Тот же аргумент с делимостью. Будем считать каждое сравнение честной монеткой. Путь из сравнений имеет вероятность , а вероятность любой перестановки — сумма таких дробей, то есть дробь со степенью двойки в знаменателе. При она не может равняться : делится на 3. Равномерности быть не может ни при каком алгоритме сортировки.
- Лишняя работа. вместо .
Корректный вариант через сортировку тоже есть: присвоить каждому элементу случайный ключ один раз и отсортировать по ключу.
def shuffle_by_keys(a): return sorted(a, key=lambda _: random.random())
Ключи независимы и почти наверняка различны (совпадение двух float на практике не случается), поэтому каждый порядок ключей равновероятен. Это честно, но медленнее Фишера–Йетса. Такой приём уместен в SQL: ORDER BY random(), где цикла с обменами нет.
Случайная выборка k элементов
Фишера–Йетса не обязательно доводить до конца. Если нужно случайных элементов из без повторов, достаточно шагов. Удобнее идти слева направо: на шаге выбираем случайный элемент из [i, n - 1] и ставим его на позицию .
def sample_k(a, k): a = a[:] n = len(a) for i in range(k): j = random.randint(i, n - 1) a[i], a[j] = a[j], a[i] return a[:k]
Сложность — обменов плюс на копию. Если массив можно портить, копия не нужна. Каждое -элементное подмножество (и даже каждый упорядоченный набор) равновероятен: первые шагов полного перемешивания дают префикс равномерной перестановки.
Проверка: 100 000 выборок по 2 из range(5). Каждое число должно встретиться около раз.
random.seed(3) cnt = Counter() for _ in range(100_000): cnt.update(sample_k(list(range(5)), 2)) print(sorted(cnt.items())) # [(0, 39902), (1, 40009), (2, 39930), (3, 40179), (4, 39980)]
Когда огромно, а мало, копировать весь массив дорого. Тогда хранят только изменённые позиции в словаре: «виртуальный» массив, где a[i] по умолчанию равно i. Получается и по времени, и по памяти.
Связь с резервуарной выборкой
Перемешивание можно вести и в обратную сторону — «изнутри наружу» (inside-out). Мы строим результат, добавляя элементы источника по одному. Очередной элемент встаёт на случайное место среди уже собранных, а вытесненный уходит в конец.
def inside_out(source): a = [] for i, x in enumerate(source): j = random.randint(0, i) if j == i: a.append(x) else: a.append(a[j]) a[j] = x return a
Эта версия не знает длину входа заранее и читает его за один проход, как поток. Здесь появляется связь с reservoir sampling. Посмотрите, как ведёт себя позиция 0 при inside-out: на шаге новый элемент занимает её с вероятностью . Это ровно правило алгоритма R для одного элемента. А первые позиций обновляются точно по правилу выборки элементов: новый элемент попадает в них с вероятностью .
Получается, что резервуарная выборка — это inside-out Фишер–Йетс, у которого мы храним только первые ячеек и выбрасываем остальное. Отсюда разделение задач:
- нужна вся перестановка — Фишер–Йетс, памяти под массив;
- нужны элементов из массива — частичный Фишер–Йетс, шагов;
- нужны элементов из потока неизвестной длины — резервуарная выборка, памяти. Подробный разбор с доказательством и задачами — в отдельной статье про reservoir sampling.
Типичные ошибки
Диапазон j без текущего элемента
def sattolo(a): for i in range(len(a) - 1, 0, -1): j = random.randint(0, i - 1) # j < i строго a[i], a[j] = a[j], a[i] return a
Ошибка на единицу, которая выглядит как оптимизация: «зачем менять элемент сам с собой?». На массиве из трёх элементов этот код выдаёт только [1, 2, 0] и [2, 0, 1] — 2 перестановки из 6. Заметить это легко, если посчитать частоты перестановок: ни один элемент никогда не остаётся на своём месте.
У этого кода есть имя — алгоритм Саттоло (1986). Он равномерно выбирает случайный цикл длины : перестановку, в которой ни один элемент не остаётся на месте и все образуют одну цепочку. Это полезно, например, чтобы сгенерировать случайный обход всех вершин или «тайного Санту», где никто не дарит подарок себе и все участники связаны в одно кольцо. Но для перемешивания это ошибка.
Наивный диапазон на весь массив
Разобран выше: путей на перестановок. Узнаётся по randint(0, n - 1) внутри цикла.
Смещение от остатка
В C и C++ часто пишут rand() % (i + 1). Если диапазон генератора не делится на , маленькие остатки выпадают чуть чаще. Для небольших это незаметно, но для честного перемешивания используйте std::uniform_int_distribution. В Python random.randint и random.randrange от этой проблемы свободны: внутри используется отбрасывание лишних значений, а не остаток.
Слабый генератор
Число перестановок колоды из 52 карт . Если генератор инициализирован 32-битным зерном, он может выдать не больше разных колод — ничтожную долю. Для игр и симуляций это обычно неважно. Для покера на деньги, лотерей и всего, что связано с безопасностью, нужен криптографический генератор: в Python это secrets.SystemRandom().shuffle(a).
Проверка на глаз
«Я запустил, и массив выглядит перемешанным» — не проверка. Наивный shuffle и sort со случайным компаратором тоже выглядят перемешанными. Минимальная проверка: прогнать перемешивание маленького массива много раз и посчитать частоты перестановок, как в примерах выше. Ещё лучше — точный перебор всех путей для .
Где это встречается на собеседованиях
- Shuffle an Array (LeetCode 384) — прямая формулировка.
- «Найдите ошибку»: показывают наивный shuffle или
sort(() => Math.random() - 0.5)и просят объяснить, что не так. Лучший ответ — аргумент с делимостью. - «Докажите равномерность»: подсчёт путей или телескопическое произведение.
- Выборки: случайные элементов из массива, случайная точка или индекс без повторов. Здесь пригодится частичный Фишер–Йетс.
- Рандомизированные алгоритмы: перемешивание входа перед быстрой сортировкой или quickselect защищает от плохих входов, подобранных под фиксированный выбор опорного элемента.
Как отвечать: сначала код Фишера–Йетса с явным комментарием про включительный диапазон [0, i]. Потом одна фраза о том, почему наивная версия смещена ( не делится на ). Потом доказательство через путей. Если спросят про поток неизвестной длины — переход к резервуарной выборке.