Перемешивание Фишера–Йетса: почему наивный shuffle смещён и как сделать честно

Алгоритм Фишера–Йетса простыми словами: почему наивный shuffle и sort со случайным компаратором дают смещение, доказательство равномерности, задача Shuffle an Array и выборка k элементов.

13 мин чтенияалгоритмы · вероятность · массивы · python

Коротко

ВопросОтвет
ЗадачаПереставить элементы массива так, чтобы каждая из n!n! перестановок выпадала с вероятностью 1/n!1/n!
АлгоритмИдём с конца: на шаге ii меняем a[i] со случайным a[j], где 0≤j≤i0 \le j \le i включительно
СложностьO(n)O(n) времени, O(1)O(1) дополнительной памяти, ровно n−1n - 1 случайных чисел
Частая ошибкаБрать jj из всего массива. Получается nnn^n исходов на n!n! перестановок, и nnn^n на n!n! не делится
ЗадачиLeetCode 384 Shuffle an Array, случайная выборка kk элементов, тасовка колоды, A/B-распределение

Перемешать массив — задача на пять строк. Ошибиться в ней можно одним символом, и программа продолжит «работать»: массив выглядит перемешанным, тесты проходят. Поэтому на собеседовании спрашивают не только код, но и то, почему он даёт равномерное распределение.

Что значит «честно перемешать»

У массива из nn различных элементов n!n! перестановок. Честное перемешивание выдаёт каждую с вероятностью 1/n!1/n!. Слабее, но полезно для проверки: каждый элемент оказывается на каждой позиции с вероятностью 1/n1/n.

Второе следует из первого, но не наоборот. Пример: циклический сдвиг массива на случайное число позиций от 00 до n−1n-1. Каждый элемент попадает на каждую позицию с вероятностью 1/n1/n, но получается всего nn перестановок из n!n!. Поэтому проверка «по позициям» — необходимая, но не достаточная.

Наивный 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)]

Всего 33=273^3 = 27 равновероятных путей, а перестановок 6. Три перестановки получаются 5 раз, три — 4 раза. Вероятности 5/27≈0,1855/27 \approx 0{,}185 и 4/27≈0,1484/27 \approx 0{,}148 вместо 1/6≈0,1671/6 \approx 0{,}167.

Аргумент через делимость

Перебор не нужен, чтобы доказать, что наивный алгоритм неравномерен. Каждый из nnn^n путей выбора равновероятен. Если бы все n!n! перестановок получались одинаково часто, то nnn^n делилось бы на n!n!. Но при n≥3n \ge 3 число n−1n - 1 делит n!n! и не делит nnn^n: у n−1n - 1 и nn нет общих делителей, кроме единицы. Значит, равномерности быть не может.

Это хороший ответ на вопрос интервьюера «а что не так с этим кодом?». Он короткий, строгий и не требует считать вероятности.

С ростом nn перекос не исчезает. Для n=4n = 4 из 256256 путей одна перестановка получается 8 раз, другая — 15. Разница почти вдвое.

Алгоритм Фишера–Йетса

Рональд Фишер и Фрэнк Йетс описали метод в 1938 году для ручной работы с таблицами случайных чисел: вычёркивали элементы из списка по одному. Компьютерную версию на месте, за O(n)O(n), опубликовал Ричард Дурстенфельд в 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], n=4n = 4.

ШагДиапазон jjВыпало jjМассив после обменаГотовый хвост
i=3i=30..30..31[A, D, C, B]B
i=2i=20..20..22[A, D, C, B]C, B
i=1i=10..10..10[D, A, C, B]A, C, B

На шаге i=2i = 2 выпало j=ij = i: элемент остался на месте. Это нормальный исход, и он обязан быть возможен. Иначе алгоритм не сможет выдать перестановки, где элемент стоит на своём месте.

Доказательство равномерности

Через подсчёт путей

На шаге ii (от n−1n-1 до 11) у jj есть i+1i + 1 вариант. Всего путей

n⋅(n−1)⋅…⋅2=n!n \cdot (n-1) \cdot \ldots \cdot 2 = n!

Все пути равновероятны. Осталось показать, что разные пути дают разные перестановки. Посмотрим на результат: элемент на позиции n−1n-1 однозначно говорит, какой jj выпал на первом шаге, потому что эта позиция больше не меняется. Дальше то же рассуждение для позиции n−2n-2 и так далее. Значит, отображение «путь → перестановка» взаимно однозначно. n!n! путей переходят в n!n! различных перестановок, каждая получается ровно одним путём, то есть с вероятностью 1/n!1/n!.

Это можно проверить перебором, как мы делали для наивной версии:

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! перестановок, каждая ровно один раз

Через вероятность для одного элемента

Иногда интервьюер просит другое рассуждение: «какова вероятность, что элемент xx окажется на позиции kk?».

Чтобы xx попал на позицию kk, нужно, чтобы на шагах n−1,n−2,…,k+1n-1, n-2, \dots, k+1 его не выбрали, а на шаге kk — выбрали. На шаге ii кандидатов i+1i + 1, и xx среди них, пока его не выбрали. Перемножаем:

n−1n⋅n−2n−1⋅…⋅k+1k+2⋅1k+1=1n\frac{n-1}{n} \cdot \frac{n-2}{n-1} \cdot \ldots \cdot \frac{k+1}{k+2} \cdot \frac{1}{k+1} = \frac{1}{n}

Произведение телескопическое: каждый числитель сокращается со знаменателем следующей дроби. Остаётся 1/n1/n для любых xx и kk.

Если эта цепочка кажется знакомой, она действительно та же, что в доказательстве резервуарной выборки. Ниже разберём, почему это не совпадение.

Задача 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 работают за O(n)O(n), память — O(n)O(n) на копию оригинала.

Что здесь проверяют на собеседовании:

  • Копию в конструкторе. Если сохранить ссылку self.original = nums, первый же shuffle испортит «оригинал», и reset вернёт перемешанный массив.
  • Копию в reset. Если reset вернёт сам self.original, а потом shuffle начнёт его менять, оригинал снова испорчен.
  • Можно ли перемешивать текущий массив, а не оригинал. Можно: перестановка случайной перестановки, перемешанной честно, — тоже равномерна. Независимо от того, с чего начинать, Фишер–Йетс выдаёт каждую перестановку с вероятностью 1/n!1/n!.

Перемешивание сортировкой

Ещё одна популярная ошибка, особенно в 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%.

Почему так:

  • Компаратор противоречив. Сортировка рассчитывает, что если a<ba < b и b<cb < c, то a<ca < c. Случайный компаратор это нарушает, и результат зависит от того, какие сравнения делает конкретный алгоритм сортировки. Цифры будут разными в разных движках и версиях.
  • Тот же аргумент с делимостью. Будем считать каждое сравнение честной монеткой. Путь из mm сравнений имеет вероятность 1/2m1/2^m, а вероятность любой перестановки — сумма таких дробей, то есть дробь со степенью двойки в знаменателе. При n≥3n \ge 3 она не может равняться 1/n!1/n!: n!n! делится на 3. Равномерности быть не может ни при каком алгоритме сортировки.
  • Лишняя работа. O(nlog⁡n)O(n \log n) вместо O(n)O(n).

Корректный вариант через сортировку тоже есть: присвоить каждому элементу случайный ключ один раз и отсортировать по ключу.

def shuffle_by_keys(a): return sorted(a, key=lambda _: random.random())

Ключи независимы и почти наверняка различны (совпадение двух float на практике не случается), поэтому каждый порядок ключей равновероятен. Это честно, но медленнее Фишера–Йетса. Такой приём уместен в SQL: ORDER BY random(), где цикла с обменами нет.

Случайная выборка k элементов

Фишера–Йетса не обязательно доводить до конца. Если нужно kk случайных элементов из nn без повторов, достаточно kk шагов. Удобнее идти слева направо: на шаге ii выбираем случайный элемент из [i, n - 1] и ставим его на позицию ii.

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]

Сложность — O(k)O(k) обменов плюс O(n)O(n) на копию. Если массив можно портить, копия не нужна. Каждое kk-элементное подмножество (и даже каждый упорядоченный набор) равновероятен: первые kk шагов полного перемешивания дают префикс равномерной перестановки.

Проверка: 100 000 выборок по 2 из range(5). Каждое число должно встретиться около 100 000⋅2/5=40 000100\,000 \cdot 2/5 = 40\,000 раз.

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)]

Когда nn огромно, а kk мало, копировать весь массив дорого. Тогда хранят только изменённые позиции в словаре: «виртуальный» массив, где a[i] по умолчанию равно i. Получается O(k)O(k) и по времени, и по памяти.

Связь с резервуарной выборкой

Перемешивание можно вести и в обратную сторону — «изнутри наружу» (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: на шаге ii новый элемент занимает её с вероятностью 1/(i+1)1/(i+1). Это ровно правило алгоритма R для одного элемента. А первые kk позиций обновляются точно по правилу выборки kk элементов: новый элемент попадает в них с вероятностью k/(i+1)k/(i+1).

Получается, что резервуарная выборка — это inside-out Фишер–Йетс, у которого мы храним только первые kk ячеек и выбрасываем остальное. Отсюда разделение задач:

  • нужна вся перестановка — Фишер–Йетс, O(n)O(n) памяти под массив;
  • нужны kk элементов из массива — частичный Фишер–Йетс, O(k)O(k) шагов;
  • нужны kk элементов из потока неизвестной длины — резервуарная выборка, O(k)O(k) памяти. Подробный разбор с доказательством и задачами — в отдельной статье про 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). Он равномерно выбирает случайный цикл длины nn: перестановку, в которой ни один элемент не остаётся на месте и все образуют одну цепочку. Это полезно, например, чтобы сгенерировать случайный обход всех вершин или «тайного Санту», где никто не дарит подарок себе и все участники связаны в одно кольцо. Но для перемешивания это ошибка.

Наивный диапазон на весь массив

Разобран выше: nnn^n путей на n!n! перестановок. Узнаётся по randint(0, n - 1) внутри цикла.

Смещение от остатка

В C и C++ часто пишут rand() % (i + 1). Если диапазон генератора не делится на i+1i + 1, маленькие остатки выпадают чуть чаще. Для небольших ii это незаметно, но для честного перемешивания используйте std::uniform_int_distribution. В Python random.randint и random.randrange от этой проблемы свободны: внутри используется отбрасывание лишних значений, а не остаток.

Слабый генератор

Число перестановок колоды из 52 карт 52!≈8⋅1067≈2225,652! \approx 8 \cdot 10^{67} \approx 2^{225{,}6}. Если генератор инициализирован 32-битным зерном, он может выдать не больше 2322^{32} разных колод — ничтожную долю. Для игр и симуляций это обычно неважно. Для покера на деньги, лотерей и всего, что связано с безопасностью, нужен криптографический генератор: в Python это secrets.SystemRandom().shuffle(a).

Проверка на глаз

«Я запустил, и массив выглядит перемешанным» — не проверка. Наивный shuffle и sort со случайным компаратором тоже выглядят перемешанными. Минимальная проверка: прогнать перемешивание маленького массива много раз и посчитать частоты перестановок, как в примерах выше. Ещё лучше — точный перебор всех путей для n=3,4,5n = 3, 4, 5.

Где это встречается на собеседованиях

  • Shuffle an Array (LeetCode 384) — прямая формулировка.
  • «Найдите ошибку»: показывают наивный shuffle или sort(() => Math.random() - 0.5) и просят объяснить, что не так. Лучший ответ — аргумент с делимостью.
  • «Докажите равномерность»: подсчёт путей или телескопическое произведение.
  • Выборки: случайные kk элементов из массива, случайная точка или индекс без повторов. Здесь пригодится частичный Фишер–Йетс.
  • Рандомизированные алгоритмы: перемешивание входа перед быстрой сортировкой или quickselect защищает от плохих входов, подобранных под фиксированный выбор опорного элемента.

Как отвечать: сначала код Фишера–Йетса с явным комментарием про включительный диапазон [0, i]. Потом одна фраза о том, почему наивная версия смещена (nnn^n не делится на n!n!). Потом доказательство через n!n! путей. Если спросят про поток неизвестной длины — переход к резервуарной выборке.

Потренироваться в спокойной обстановке

Все задачи