Тасование Фишера — Йетса (названо в честь Рональда Фишера и Фрэнка Йейтса, известно также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Вариант тасования Фишера — Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера — Йетса несмещённый, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, и не требует дополнительной памяти.
Основная процедура тасования Фишера — Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
Оригинальный метод Фишера — Йетса Тасование Фишера — Йетса, в его первоначальном виде, было описано в 1938 году Рональдом Фишером и Фрэнком Йетсом в их книге Статистические таблицы для исследований в области биологии, архитектуры и медицины. (Замечание: шестое издание, ISBN 0-02-844720-4, доступно в сети , но оно дает другой алгоритм тасования — алгоритм C. R. Rao) (Последнее издание книги описывает другой алгоритм тасования, приписываемый К. Р. Рао.) Их метод был разработан для карандаша и бумаги и использовал вычисленные заранее таблицы случайных чисел как источник случайности. Выглядел он следующим образом:
Запишем числа от 1 до N. Выберем случайное число k в диапазоне { 1, D }, где D - число оставшихся чисел. Числа 1 и D включаются. Вычеркиваем k-е оставшееся число, отсчитывая числа в порядке возрастания, и записываем его где-нибудь. Повторяем шаг 2, пока все числа не будут выбраны. Последовательность чисел, записанных на шаге 3, является случайной перестановкой.
Если числа, используемые на шаге 2, действительно случайны и не смещены, мы получим такими же и случайные перестановки (случайны и не смещены). Фишер и Йетс описали, каким образом получить такие случайные числа для любого интервала, и предоставили таблицы, позволяющие избежать смещения. Они также предполагали возможность упростить метод — выбирать случайные числа от единицы до N, и, затем, отбрасывать повторения — для генерации половины генерируемой перестановки, и только потом использовать более сложный алгоритм для оставшейся половины, в противном случае повторяющиеся числа будут попадаться слишком часто.
Современный алгоритм Современный вариант алгоритма тасования Фишера — Йетса, предназначенный для использования в компьютерах, был представлен Ричардом Дурштенфельдом (Richard Durstenfeld) в 1964-м году в журнале Communications of the ACM том 7, выпуск 7, под названием «Algorithm 235: Random permutation»Durstenfeld, Richard (July 1964). «Algorithm 235: Random permutation». Communications of the ACM 7 (7): 420., и был популяризован Дональдом Кнутом во втором томе его книги «Искусство программирования» как «Алгоритм P». Ни Дурштенфельд, ни Кнут в первом издании книги не упомянули об алгоритме Фишера и Йетса, и, похоже, не были осведомлены о нём. Во втором издании книги «Искусство программирования», однако, это упущение было исправлено
Алгоритм, описанный Дурштенфельдом, отличается от алгоритма Фишера и Йетса в небольших, но существенных деталях. Чтобы компьютерная реализация алгоритма не тратила бесполезно время на перебор оставшихся чисел на шаге 3, у Дурштенфельда на каждой итерации выбираемые числа переносились в конец списка путём перестановки с последним невыбранным числом. Эта модификация сокращала временную сложность алгоритма до O(n), по сравнению с O(n2) для исходного алгоритма. Это изменение приводит к следующему алгоритму.
Для тасования массива a из n элементов (индексы 0..n-1): для всех i от n − 1 до 1 выполнить j ← случайное число 0 ≤ j ≤ i обменять местами a[j] и a[i]
«Вывернутый» алгоритм Тасование Фишера — Йетса в варианте Дурштенфельда является тасованием на месте. То есть, при задании заполненного массива, он тасует элементы в том же массиве, а не создает копию массива с переставленными элементами. Это может дать существенное преимущество при тасовании больших массивов.
Одновременная инициализация и тасование массива может немного увеличить эффективность, если использовать «вывернутую» версию тасования. В этой версии исходный элемент с индексом i переносится в случайную позицию среди первых i позиций после того, как с этой позиции будет перенесен элемент на позицию i. В случае выбора случайного числа, равного i, будет сначала перенесено неприсвоенное значение, но оно будет тотчас же затерто правильным значением. Никакой отдельной инициализации в этом варианте не нужно, и никаких перестановок не осуществляется. Если источник определяется простой функцией, как, например, целые числа от 0 до n — 1, источник может быть просто заменен этой функцией, поскольку источник никогда не меняется во время выполнения.
Для создания массива a из n случайно перетасованных элементов источника: for i from 0 to n − 1 do j ← random integer with 0 ≤ j ≤ i a[i] ← a[j] a[j] ← source[i]
Корректность «вывернутого» тасования можно доказать по индукции; любая из n! различных последовательностей случайных чисел, получаемых во время работы алгоритма образует свою собственную перестановку, так что все перестановки будут получены только один раз.
Другое преимущество этого подхода состоит в том, что, даже не зная числа «n», числа элементов источника, мы можем создавать равномерно распределенные перестановки. Ниже массив a создается итеративно, начиная с пустого и a.length представляет его текущую длину.
пока источник.естьЕще j ← случайное число 0 ≤ j ≤ a.length если j = a.length a.добавить(источник.следующийЭлемент) в противном случае a.добавить(a[j]) a[j] ← источник.следующийЭлемент
Примеры
С карандашом и бумагой В качестве примера, переставим числа от 1 до 24, используя оригинальный метод Фишера — Йетса. Для начала выпишем числа на бумаге:
Интервал Выбрано Черновик Результат 1 2 3 4 5 6 7 8
Теперь возьмем случайное число k от 1 до 8 — пусть это будет 3 — и вычеркнем k-е (то есть третье) число (3, конечно) и переносим его в результирующую последовательность:
Интервал Выбрано Черновик Результат 1-8 3 1 2 3 4 5 6 7 8 3
Теперь выбираем второе случайное число, на этот раз из интервала 1—7, пусть это будет 4. Теперь вычеркиваем четвёртое ещё не вычеркнутое число из черновика — это будет число 5 — и добавим его в результат:
Интервал Выбрано Черновик Результат 1-7 4 1 2 3 4 5 6 7 8 3 5
Теперь мы выбираем случайное число из интервала 1—6, затем из интервала 1—5, и так далее, повторяя процесс вычеркивания, как описано выше:
Интервал Выбрано Черновик Результат 1-6 5 1 2 3 4 5 6 7 8 3 5 7 1-5 3 1 2 3 4 5 6 7 8 3 5 7 4 1-4 4 1 2 3 4 5 6 7 8 3 5 7 4 8 1-3 1 1 2 3 4 5 6 7 8 3 5 7 4 8 1 1-2 2 1 2 3 4 5 6 7 8 3 5 7 4 8 1 6 1 2 3 4 5 6 7 8 3 5 7 4 8 1 6 2
Современный метод Сделаем то же самое с помощью метода Дурштенфельда. На этот раз, вместо вычеркивания выбранных чисел и копирования их куда-либо, мы переставляем их с ещё не выбранными числами. Как и раньше, начнем с выписывания чисел от 1 до 8:
Интервал Выбрано Черновик Результат 1 2 3 4 5 6 7 8
Выберем первое случайное число от 1 до 8, пусть это будет 6, так что переставляем местами 6-е и 8-е числа в списке:
Интервал Выбрано Черновик Результат 1-8 6 1 2 3 4 5 8 7 6
Следующее случайное число мы выбираем из интервала 1 — 7, и пусть это будет 2. Теперь мы переставляем 2-е и 7-е числа:
Интервал Выбрано Черновик Результат 1-7 2 1 7 3 4 5 8 2 6
Следующее случайное число мы выбираем из интервала 1 — 6, и пусть это будет 6, что означает, что нам следует оставить 6-е число на месте (после предыдущих перестановок здесь стоит число 8). Продолжаем действовать таким образом, пока вся перестановка не будет сформирована:
Интервал Выбрано Черновик Результат 1-6 6 1 7 3 4 5 8 2 6 1-5 1 5 7 3 4 1 8 2 6 1-4 3 5 7 4 3 1 8 2 6 1-3 3 5 7 4 3 1 8 2 6 1-2 1 7 5 4 3 1 8 2 6
Варианты
Алгоритм Саттоло Очень похожий алгоритм был опубликован в 1986 году Сандрой Саттоло (Sandra Sattolo) для генерации равномерно распределенных циклов (максимальной) длины n. Разница между алгоритмами Дурштенфельда и Саттоло заключается лишь в шаге 2 — в алгоритме Саттоло случайное число j выбирается из интервала 1 — i−1, а не из 1 — i. Эта простая модификация приводит к перестановкам, состоящим из одного цикла.
Фактически, как описано ниже, легко случайно реализовать алгоритм Саттоло при попытке создать алгоритм Фишера — Йетса. Такая ошибка приводит к генерации перестановок из меньшего множества (n−1)! циклов длины N, вместо полного множества из n! возможных перестановок.
То, что алгоритм Саттоло всегда создает цикл длины n, может быть показано по индукции. Предположим, что после первой итерации (переставившей элемент n на позицию k < n) остальные n − 1 итераций образовали цикл элементов длиной n − 1. Проследим цепочку перемещений — возьмем какой-либо элемент, он переместится на некоторую позицию p, вытеснив элемент, находившийся там, на некоторую новую позицию, и так далее. По принятому предположению мы попадем на начальную позицию, только перебрав все остальные позиции. Последний элемент, после перемещения на позицию k, и последовательных перестановок первых n − 1 элементов попадет на позицию l; сравним перестановку π всех n элементов с перестановкой σ первых n − 1 элементов. Отслеживая перестановки, как было упомянуто выше, мы не найдем разницу между π и σ, пока не достигнем позиции k. В π элемент, находящийся на позиции k, переместится на последнюю позицию, а не на позицию l, а элемент, находящийся на последней позиции, попадет на место l. Начиная с этого места последовательность перемещений элементов π снова будет совпадать с σ, и все позиции будут пройдены перед возвратом на начальную позицию, что и требовалось.
Как и в случае доказательства равновероятности перестановок, нам достаточно показать, что алгоритм Саттоло создает (n−1)! различных перестановок, которые, ввиду предполагаемой несмещенности генератора случайных чисел, имеют равную вероятность. (n−1)! различных перестановок, генерируемых алгоритмом, в точности покрывают множество циклов длины n.
Простая реализация алгоритма Саттоло на языке Python:
from random import randrange
def sattoloCycle(items): i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j] return
Сравнение с другими алгоритмами тасования Алгоритм Фишера — Йетса вполне эффективен, и даже более того, его скорость и затраты памяти асимптотически оптимальны. При использовании высококачественного несмещенного генератора случайных чисел алгоритм гарантирует несмещенный результат. У алгоритма существует ещё одно преимущество — если требуется получить некоторую часть перестановок, алгоритм может быть остановлен на полпути или даже остановлен и возобновлен многократно.
Существует альтернативный метод — каждому элементу множества присваивается случайное число, а затем множество сортируется согласно присвоенным числам. Асимптотическая оценка скорости сортировки в лучшем случае равна O(n log n), что несравнимо с оценкой O(n) скорости работы алгоритма Фишера — Йетса. Как и тасование Фишера — Йетса, сортирующий метод дает несмещенные перестановки, но он менее чувствителен к возможным проблемам генератора случайных чисел. Однако следует уделить особое внимание генерации случайных чисел, чтобы избежать повторения, поскольку алгоритм с сортировкой, в общем случае, не сортирует элементы случайно.
Существует вариант метода с сортировкой, в котором список сортируется с использованием функции сравнения, возвращающей случайное число. Однако это исключительно плохой метод: он с большой вероятностью образует неравномерное распределение, вдобавок зависящее от метода используемой сортировки .