SRT Поиск и сортировка Алгоритм
Перемешивание Фишера — Йетса
Также: Fisher–Yates shuffle · Knuth shuffle · тасовка Кнута · алгоритм Дурстенфельда · случайная перестановка · random permutation · shuffle
Как перемешать массив так, чтобы каждая из n! перестановок выпадала с одной и той же вероятностью: справа налево ставить на место i случайный элемент из ещё не тронутых. Четыре строки кода — и две популярные ошибки рядом, обе с настоящими историями: бюллетень браузеров 2010 года и онлайн-покер 1999-го.
В 2010 году части пользователей Windows стали показывать экран выбора браузера: пять крупных браузеров в случайном порядке, чтобы ни один не получал преимущества первого места. Роб Уир взял код этого экрана, прогнал его 10 000 раз в Internet Explorer и увидел, что сам Internet Explorer стоит последним в половине случаев, а не в каждом пятом. Браузеры перемешивали сортировкой, у которой сравнение отвечало наугад. Ниже те же пять браузеров тасует ваш браузер — тем же способом, наивным обменом и правильным алгоритмом. Посмотрите, где цвет уходит дальше шума.
Сортировка со случайным сравнением даёт перекос на десяток процентных пунктов и больше, и в каждом браузере свой: результат зависит от того, в каком порядке встроенная сортировка сравнивает элементы. Обмен «с любым» перекошен меньше, но тоже далеко за пределами шума. И только третий способ даёт ровные 20 % во всех клетках — с точностью до случайных колебаний, которые сцена показывает рядом.
Идея
Пройдём массив справа налево. На место i поставим случайный элемент из ещё не тронутых — с мест от 0 до i включительно, — обменяв его с тем, что стоит на месте i. После этого место i больше не трогаем. Получается одна случайная перестановка из n!, и все они равновероятны.
Это ровно то, что делает человек, вытягивая карты из шапки по одной: каждая следующая — случайная из оставшихся. Хитрость только в том, что «оставшиеся» хранятся в той же самой части массива: вытянутую карту меняют местами с последней из оставшихся, и невытянутые снова лежат подряд. Ни дополнительной памяти, ни удалений из середины.
Почему каждая перестановка равновероятна
Если каждое ji выбирается равновероятно из {0, …, i} и независимо от остальных, то каждая из n! перестановок получается с вероятностью ровно 1/n!.
Алгоритм делает n − 1 выбор: jn−1 из n вариантов, jn−2 из n − 1, …, j1 из двух. Всего наборов n·(n − 1)·…·2 = n!, и все равновероятны. Покажем, что разные наборы дают разные перестановки: тогда соответствие наборов и перестановок взаимно однозначно, и каждая перестановка получается ровно из одного набора, с вероятностью 1/n!.
По итоговой перестановке набор восстанавливается. После шага i место i больше не меняется, значит, элемент, который стоит там в конце, попал туда на шаге i. Повторим алгоритм с исходного массива: перед шагом i найдём, где сейчас лежит этот элемент, — это и есть ji. Каждый выбор вычислен однозначно, значит, двух наборов с одной перестановкой нет.
Восстановление набора по перестановке — первая задача в конце статьи. А сам набор (jn−1, …, j1) — это запись номера перестановки в факториальной системе счисления, где у i-й цифры основание i + 1.
Ошибка первая: обмен с любым
Самая частая ошибка — менять каждый элемент не с ещё не тронутым, а с любым:
for i in range(n):
j = random.randrange(n) # должно быть randrange(i, n) или, справа налево, randrange(i + 1)
a[i], a[j] = a[j], a[i]Выглядит даже «случайнее»: каждый элемент меняется с любым. Но честным это быть не может, и чтобы это увидеть, не нужно ни одного запуска.
При n ≥ 3 обмен «с любым» не даёт равновероятных перестановок.
Алгоритм делает n равновероятных выборов из n вариантов: всего nn одинаково вероятных цепочек. Если бы все n! перестановок были равновероятны, каждой досталось бы nn/n! цепочек — целое число. Но n − 1 делит n!, а с nn общих делителей не имеет: соседние числа n − 1 и n взаимно просты. Значит, n! не делит nn при n − 1 ≥ 2.
На трёх картах всё видно руками. 27 цепочек ложатся на шесть раскладов так: ACB, BAC и BCA — по 5 цепочек, ABC, CAB и CBA — по 4. Первые три выпадают с вероятностью 18,5 % вместо 16,7 %, остальные — 14,8 %. Чтобы увидеть, как перекос растёт, следите за одной картой: на каждом шаге она остаётся на месте или переезжает, и вероятности считаются точно, без единого броска.
В колоде из 52 карт вторая карта оказывается наверху на 35 % чаще положенного, а последняя — на 26 % реже. Первый столбец и последний столбец ровные: первая карта на первом же шаге уходит в случайное место, а на последнее место последний шаг кладёт случайную карту. Перекос живёт внутри, и он не исчезает с ростом колоды. Дэвид Роббинс и Итан Болкер разобрали его точно в 1981 году, а позже Дэниел Голдстейн и Дэвид Моус доказали неожиданное: начиная с 18 карт самая вероятная перестановка «наивной» тасовки — тождественная, колода как была.
Ошибка вторая: сортировка со случайным сравнением
Экран выбора браузера перемешивал примерно так: list.sort(function () { return 0.5 - Math.random(); }) — сортировка, которой на вопрос «кто меньше» отвечают монеткой. Сортировка рассчитывает, что сравнение последовательно: если A < B и B < C, то A < C. Монетка это нарушает, и что получится, зависит от того, кого с кем и в каком порядке сравнивает конкретная сортировка. Сортировка вставками, например, сравнивает последний элемент с предпоследним и при первом же ответе «не меньше» оставляет его на месте — в половине случаев. Какой сортировкой пользовался тогда Internet Explorer, для вывода неважно: честной с монеткой не бывает ни одна.
Можно ли подобрать сортировку, которая с монеткой даст честный результат? Нельзя, и причина та же, что у обмена «с любым». Каждая цепочка ответов монетки имеет вероятность 2−k, и вероятность любой перестановки — сумма таких дробей, то есть дробь со знаменателем-степенью двойки. А 1/n! при n ≥ 3 так не записать: в n! есть множитель 3. Честный способ через сортировку есть, но другой: дать каждому элементу случайный ключ — например, случайное число с плавающей точкой — и отсортировать по ключам. Это верно, если ключи не совпадают, и стоит O(n log n) вместо O(n).
Код
Фишер — Йетс и обмен «с любым» на одном генераторе: по 120 000 тасовок трёх карт, точный счёт 27 цепочек и таблица — сколько бит случайности нужно, чтобы получить любую перестановку.
Обратите внимание на below. Случайное число от 0 до m − 1 нельзя получить как x % m из 16-битного x: 65 536 не делится на 3, и остатки 0 и 1 выпадали бы на одну шестидесятипятитысячную чаще остатка 2. Здесь неполный последний отрезок отбрасывают и тянут заново. Библиотечные функции — random.randrange, rand.IntN — делают это сами.
Вторая программа — сортировка с монеткой вместо сравнения на настоящих сортировках Python и Go. Таблицы у них разные: Python сортирует слиянием с вставками, Go — вставками на коротких срезах, и у Go последний элемент остаётся последним в половине случаев — так же часто, как Internet Explorer в 2010 году.
Сколько нужно случайности
Честный алгоритм — половина дела. Чтобы любая из 52! раскладок колоды могла выпасть, генератору нужно хотя бы log2 52! ≈ 225,6 бита состояния. Иначе разных раскладок будет не больше, чем разных состояний генератора, и почти все раскладки не выпадут никогда.
В 1999 году специалисты по безопасности Reliable Software Technologies разобрали тасовку онлайн-покера: её код сервер Planet Poker опубликовал сам, чтобы показать честность игры. В тасовке были обе болезни сразу — обмен «с любым» и ошибка на единицу, из-за которой последняя карта никогда не оставалась на месте. Но главное было в генераторе: его начальное значение бралось из числа миллисекунд с полуночи. Таких значений в сутках 86 400 000 — около 226,4 раскладок из 2225,6. Сверив часы с сервером, авторы сужали поиск до примерно 200 000 вариантов, а по двум своим картам и трём открытым находили всю раздачу за доли секунды.
Обычные генераторы для этого тоже не годятся. Вихрь Мерсенна в Python имеет период 219937 − 1, и в документации прямо сказано: самая длинная последовательность, все перестановки которой он может выдать, — 2080 элементов. Для денег и секретов берут криптографический генератор — secrets в Python, crypto/rand в Go: важно не только сколько у него состояния, но и что его нельзя предсказать по выходу.
Сколько это стоит
O(n) времени: n − 1 случайное число и столько же обменов. O(1) дополнительной памяти: перемешивание на месте. Если нужен не весь массив, а случайные k элементов, достаточно первых k шагов: O(k). А если элементы приходят потоком и n заранее неизвестно, работает родственный приём — резервуарная выборка.
Один символ меняет и результат. Если выбирать j из {0, …, i − 1}, исключив само i, получится алгоритм Саттоло (1986): он выдаёт случайную перестановку из одного цикла, где ни один элемент не остаётся на месте и, переходя от элемента к его месту, обойдёшь все. Иногда это нужно, но чаще такая замена — ошибка, после которой тасовка никогда не оставляет карту на месте.
История
Рональд Фишер и Фрэнк Йетс описали способ в 1938 году в книге статистических таблиц для биологов, агрономов и медиков — для работы вручную: выписать числа от 1 до n, по таблице случайных чисел выбрать одно из оставшихся, вычеркнуть, повторить. Вычёркивание делало ручной способ медленным для машины. В 1964 году Ричард Дурстенфельд в заметке «Algorithm 235: Random permutation» в Communications of the ACM записал вариант с обменом на месте — тот, что выше. Дональд Кнут привёл его в «Искусстве программирования» как алгоритм P, поэтому его зовут ещё тасовкой Кнута.
Задачи
В первой задаче по раскладу колоды нужно восстановить числа, которые выдал генератор, — это и есть доказательство честности из раздела выше. Во второй — точная вероятность того, что «наивная» тасовка переложит карту с места a на место b: следить нужно за одной картой и всего одним проходом.
Код тасовки Нечестная тасовка