Перетасовка Фишера -Йейтса — это алгоритм перетасовки конечной последовательности . Алгоритм берет список всех элементов последовательности и постоянно определяет следующий элемент в перетасованной последовательности, случайным образом извлекая элемент из списка до тех пор, пока элементов не останется. [1] Алгоритм создает несмещенную перестановку: каждая перестановка одинаково вероятна. Современная версия алгоритма требует времени, пропорционального количеству перетасовываемых предметов, и перетасовывает их на месте .
Перетасовка Фишера-Йейтса названа в честь Рональда Фишера и Фрэнка Йейтса , которые впервые ее описали, а также известна как перетасовка Кнута в честь Дональда Кнута . [2] Вариант перетасовки Фишера-Йейтса, известный как алгоритм Саттоло , может использоваться для генерации случайных циклических перестановок длины n вместо случайных перестановок.
Тасовка Фишера-Йейтса в своей первоначальной форме была описана в 1938 году Рональдом Фишером и Фрэнком Йейтсом в их книге «Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований ». [3] В описании алгоритма использовались карандаш и бумага; таблица случайных чисел обеспечивала случайность. Основной метод генерации случайной перестановки чисел от 1 до N заключается в следующем:
При условии, что случайные числа, выбранные на шаге 2 выше, действительно случайны и несмещены, такой же будет и результирующая перестановка. Фишер и Йейтс постарались описать, как получить такие случайные числа в любом желаемом диапазоне из предоставленных таблиц таким образом, чтобы избежать какой-либо предвзятости. Они также предложили возможность использовать более простой метод — выбор случайных чисел от одного до N и отбрасывание всех дубликатов — для создания первой половины перестановки и применение более сложного алгоритма только к оставшейся половине, где выбор повторяющегося числа приведет к в противном случае они станут удручающе обычным явлением.
Современная версия перетасовки Фишера-Йейтса, разработанная для использования на компьютере, была представлена Ричардом Дюрстенфельдом в 1964 году [4] и популяризирована Дональдом Э. Кнутом в книге «Искусство компьютерного программирования » как «Алгоритм P (перетасовка)». [5] Ни в статье Дёрстенфельда, ни в первом издании Кнута « Искусство компьютерного программирования» не были отмечены работы Фишера и Йейтса; они, возможно, не знали об этом. [ нужна цитация ] Последующие издания книги Кнута «Искусство компьютерного программирования» упоминают вклад Фишера и Йейтса. [6]
Алгоритм, описанный Дюрстенфельдом, более эффективен, чем алгоритм, предложенный Фишером и Йейтсом: в то время как наивная компьютерная реализация метода Фишера и Йейтса потребовала бы ненужных затрат времени на подсчет оставшихся чисел на шаге 3 выше, решение Дюрстенфельда состоит в том, чтобы переместить «выбранные» числа. в конец списка, заменяя их последним невычеркнутым номером на каждой итерации. Это снижает временную сложность алгоритма по сравнению с наивной реализацией. [7] Это изменение дает следующий алгоритм (для массива с нулевым индексом ).
-- Чтобы перетасовать массив a из n элементов (индексы 0.. n -1): для i от n −1 до 1 сделать j ← случайное целое число такое, что 0 ≤ j ≤ i поменяйте местами a [ j ] и a [ i ]
Эквивалентная версия, которая перемешивает массив в противоположном направлении (от наименьшего индекса к наибольшему):
-- Чтобы перетасовать массив a из n элементов (индексы 0.. n -1): для i от 0 до n −2 сделать j ← случайное целое число такое, что i ≤ j < n поменять местами a [ i ] и a [ j ]
В этом примере буквы от A до H переставляются с использованием оригинального метода Фишера и Йейтса, начиная с букв в алфавитном порядке:
Выбирается случайное число j от 1 до 8. Если, например, j =3, то вычеркивают третью букву в блокноте и записывают ее как результат:
Выбирается второе случайное число, на этот раз от 1 до 7. Если число равно 4, то вычеркивают еще не вычеркнутую из блокнота четвертую букву и прибавляют ее к результату:
Следующее случайное число выбирается от 1 до 6, затем от 1 до 5 и так далее, всегда повторяя процесс вычеркивания, как указано выше:
В версии алгоритма Дюрстенфельда вместо того, чтобы вычеркивать выбранные буквы и копировать их в другом месте, они заменяются местами с последней еще не выбранной буквой. Начиная с букв от А до Н, как и раньше:
Выберите случайное число j от 1 до 8, а затем поменяйте местами j -ю и 8-ю буквы. Итак, если случайное число равно, например, 6, поменяйте местами 6-ю и 8-ю буквы в списке:
Следующее случайное число выбирается от 1 до 7, а выбранная буква меняется местами с 7-й буквой. Например, если это 2, поменяйте местами 2-ю и 7-ю буквы:
Процесс повторяется до завершения перестановки:
После восьми шагов алгоритм завершен, и полученная перестановка — GEDCAHB F.
Перетасовка Фишера-Йейтса, реализованная Дюрстенфельдом, представляет собой перетасовку на месте . То есть, учитывая предварительно инициализированный массив, он перемешивает элементы массива на месте, а не создает перетасованную копию массива. Это может быть преимуществом, если перемешиваемый массив большой.
Чтобы одновременно инициализировать и перетасовать массив, немного большей эффективности можно достичь, выполнив версию перетасовки «наизнанку». В этой версии элемент с номером i последовательно помещается в случайную позицию среди первых i позиций массива после перемещения элемента, ранее занимавшего эту позицию, на позицию i . В случае, если случайной позицией оказывается номер i , это «перемещение» (в то же место) включает неинициализированное значение, но это не имеет значения, поскольку значение затем немедленно перезаписывается. Никакой отдельной инициализации не требуется, и обмен не выполняется. В общем случае, когда источник определяется некоторой простой функцией, например целыми числами от 0 до n - 1, источник можно просто заменить функцией, поскольку источник никогда не изменяется во время выполнения.
Чтобы инициализировать массив a из n элементов случайным образом перетасованной копией источника , оба отсчитываются от 0: для i от 0 до n - 1 выполните j ← случайное целое число, такое что 0 ≤ j ≤ i , если j ≠ i a [ i ] ← a [ j ] a [ j ] ← источник [ i ]
С помощью индукции можно убедиться в правильности перетасовки наизнанку . Предполагая идеальный генератор случайных чисел, каждый из n ! разные последовательности случайных чисел, которые могут быть получены в результате вызовов функции random , дадут разные перестановки значений, поэтому все они получаются ровно один раз. Условие, проверяющее, является ли j ≠ i , может быть опущено в языках, в которых нет проблем с доступом к неинициализированным значениям массива. Это исключает n условных ветвей с ожидаемой стоимостью H n ≈ ln n + γ избыточных назначений.
Еще одним преимуществом этого метода является то, что n , количество элементов в источнике , не нужно знать заранее; нам нужно только иметь возможность определять конец исходных данных при его достижении. Ниже массив a строится итеративно, начиная с пустого, а .length представляет текущее количество видимых элементов.
Чтобы инициализировать пустой массив a случайно перетасованной копией источника , длина которой неизвестна : _ _ _ _ _ _ _ _ else a .append( a [ j ]) a [ j ] ← источник .next
Очень похожий алгоритм был опубликован в 1986 году Сандрой Саттоло для генерации равномерно распределенных циклов (максимальной) длины n . [8] [9] Единственная разница между алгоритмами Дюрстенфельда и Саттоло заключается в том, что в последнем на шаге 2 выше случайное число j выбирается из диапазона от 1 до i -1 (а не от 1 до i ) включительно. Это простое изменение модифицирует алгоритм так, что результирующая перестановка всегда состоит из одного цикла.
На самом деле, как описано ниже, довольно легко случайно реализовать алгоритм Саттоло, когда предполагается обычная перетасовка Фишера-Йейтса. Это приведет к искажению результатов, поскольку перестановки будут выбираться из меньшего набора ( n −1)! циклов длины N , а не из полного набора всех n ! возможные перестановки.
Тот факт, что алгоритм Саттоло всегда создает цикл длины n, можно показать с помощью индукции . Предположим по индукции, что после начальной итерации цикла оставшиеся итерации переставляют местами первые n - 1 элементов в соответствии с циклом длины n - 1 (эти оставшиеся итерации представляют собой просто алгоритм Саттоло, примененный к этим первым n - 1 элементам). Это означает, что, отслеживая начальный элемент до его новой позиции p , затем элемент, первоначально находившийся в позиции p , до его новой позиции и т. д., можно вернуться в исходную позицию только после посещения всех остальных позиций. Предположим, что начальная итерация поменяла местами последний элемент на элемент в (неконечной) позиции k , и что последующая перестановка первых n - 1 элементов затем переместила его в позицию l ; мы сравниваем перестановку π всех n элементов с оставшейся перестановкой σ первых n − 1 элементов. При отслеживании последовательных позиций, как только что упоминалось, нет никакой разницы между π и σ до тех пор, пока не будет достигнута позиция k . Но тогда под π элемент, первоначально находившийся в позиции k , перемещается в конечную позицию, а не в позицию l , а элемент, первоначально находившийся в конечной позиции, перемещается в позицию l . С этого момента последовательность позиций для π снова следует последовательности для σ , и все позиции будут посещены, прежде чем вернуться в исходную позицию, как и требуется.
Что касается равновероятности перестановок, то достаточно заметить, что модифицированный алгоритм включает ( n −1)! создаются различные возможные последовательности случайных чисел, каждая из которых явно дает различную перестановку, и каждая из которых возникает - при условии, что источник случайных чисел несмещен - с равной вероятностью. ( n −1)! различные произведенные таким образом перестановки точно исчерпывают набор циклов длины n : каждый такой цикл имеет уникальное обозначение цикла со значением n в конечной позиции, что допускает ( n −1)! перестановки остальных значений для заполнения остальных позиций обозначения цикла.
Пример реализации алгоритма Саттоло на Python :
из случайного импорта randrangedef sattolo_cycle ( items ) -> None : """Алгоритм Саттоло.""" i = len ( items ) while i > 1 : i = i - 1 j = randrange ( i ) # 0 <= j <= i-1 предметы [ j ], предметы [ i ] = предметы [ i ], предметы [ j ] Асимптотическая временная и пространственная сложность перетасовки Фишера-Йейтса оптимальна. В сочетании с высококачественным источником несмещенных случайных чисел он также гарантированно дает несмещенные результаты. По сравнению с некоторыми другими решениями оно также имеет то преимущество, что, если требуется только часть полученной перестановки, ее можно остановить на полпути или даже остановить и перезапустить несколько раз, генерируя перестановку постепенно по мере необходимости.
Наивный метод замены каждого элемента другим элементом, выбранным случайным образом из всех элементов, является предвзятым. [10] Различные перестановки будут иметь разные вероятности возникновения для каждого , потому что количество различных перестановок не делит поровну количество случайных результатов алгоритма . В частности, по постулату Бертрана между и будет хотя бы одно простое число , и это число будет делить, но не делить .
из случайного импорта randrangedef naive_shuffle ( items ) -> None : """Наивный метод. Это пример того, чего не следует делать — вместо этого используйте Fisher-Yates.""" n = len ( items ) для i в диапазоне ( n ): j = randrange ( n ) # 0 <= j <= n-1 элементов [ j ], элементов [ i ] = элементов [ i ], элементов [ j ] Альтернативный метод присваивает случайное число каждому элементу перетасовываемого набора, а затем сортирует набор в соответствии с присвоенными номерами. Метод сортировки имеет ту же асимптотическую временную сложность, что и метод Фишера-Йейтса: хотя общая сортировка составляет O ( n log n ), числа эффективно сортируются с использованием сортировки по основанию за время O ( n ). Подобно перетасовке Фишера-Йейтса, метод сортировки дает несмещенные результаты. Однако необходимо позаботиться о том, чтобы присвоенные случайные числа никогда не дублировались, поскольку алгоритмы сортировки обычно не упорядочивают элементы случайным образом в случае равенства. [11] Кроме того, этот метод требует асимптотически большего пространства: O ( n ) дополнительного места для хранения случайных чисел по сравнению с O (1) пространства для перетасовки Фишера-Йейтса. Наконец, метод сортировки имеет простую параллельную реализацию, в отличие от перетасовки Фишера-Йейтса, которая является последовательной.
Вариант описанного выше метода, который нашел некоторое применение в языках, поддерживающих сортировку с помощью определяемых пользователем функций сравнения, заключается в перетасовке списка путем его сортировки с помощью функции сравнения, возвращающей случайные значения. Однако это, скорее всего, приведет к крайне неравномерному распределению, которое, кроме того, сильно зависит от используемого алгоритма сортировки. [12] [13] Например, предположим, что в качестве алгоритма сортировки используется быстрая сортировка с фиксированным элементом, выбранным в качестве первого элемента поворота . Алгоритм начинает сравнивать опорный элемент со всеми другими элементами, чтобы разделить их на меньшие и большие, а относительные размеры этих групп будут определять окончательное место опорного элемента. Для равномерно распределенной случайной перестановки каждая возможная конечная позиция должна быть одинаково вероятной для опорного элемента, но если каждое из начальных сравнений возвращает «меньше» или «больше» с равной вероятностью, тогда эта позиция будет иметь биномиальное распределение для p = 1/2, что дает позиции ближе к середине последовательности с гораздо более высокой вероятностью, чем позиции ближе к концам. Функции рандомизированного сравнения, применяемые к другим методам сортировки, таким как сортировка слиянием , могут давать результаты, которые кажутся более однородными, но это не совсем так, поскольку объединение двух последовательностей путем многократного выбора одной из них с равной вероятностью (пока выбор не будет вызван исчерпанием одной последовательность) не дает результатов с равномерным распределением; вместо этого вероятность выбора последовательности должна быть пропорциональна количеству оставшихся в ней элементов . Фактически ни один метод, который использует только двусторонние случайные события с равной вероятностью ( «подбрасывание монеты» ), повторяемые ограниченное число раз, не может производить перестановки последовательности (более двух элементов) с равномерным распределением, поскольку каждое выполнение вероятностью пути будет рациональное число со знаменателем, степенью 2 , а требуемая вероятность 1/ n ! ибо каждая возможная перестановка не имеет такой формы .
В принципе, этот метод перетасовки может даже привести к сбоям программы, таким как бесконечные циклы или нарушения доступа, поскольку правильность алгоритма сортировки может зависеть от свойств отношения порядка (например, транзитивности ), которых определенно не будет при сравнении, производящем случайные значения. [14] Хотя такое поведение не должно происходить с процедурами сортировки, которые никогда не выполняют сравнение, результат которого можно с уверенностью предсказать (на основе предыдущих сравнений), могут быть веские причины для преднамеренного проведения таких сравнений. Например, тот факт, что любой элемент должен сравниваться равным самому себе, позволяет использовать его в качестве контрольного значения по соображениям эффективности, и в этом случае функция случайного сравнения нарушит алгоритм сортировки.
Необходимо соблюдать осторожность при реализации перетасовки Фишера-Йейтса, как при реализации самого алгоритма, так и при генерации случайных чисел, на которых он построен, иначе результаты могут показать заметное смещение. Ниже перечислен ряд распространенных источников предвзятости.
Распространенной ошибкой при реализации перетасовки Фишера-Йейтса является выбор случайных чисел из неправильного диапазона. Может показаться, что ошибочный алгоритм работает правильно, но он не будет выдавать все возможные перестановки с равной вероятностью, а может вообще не выдавать определенные перестановки. Например, распространенной ошибкой отклонения на единицу будет выбор индекса j записи для замены в приведенном выше примере, который всегда будет строго меньше индекса i записи, с которой она будет заменена. Это превращает перетасовку Фишера-Йейтса в алгоритм Саттоло, который производит только перестановки, состоящие из одного цикла, включающего все элементы: в частности, с этой модификацией ни один элемент массива никогда не сможет оказаться в исходном положении.
Аналогично, всегда выбор j из всего диапазона допустимых индексов массива на каждой итерации также дает результат, который является предвзятым, хотя и менее очевидным. Это видно из того факта, что при этом получается n n различных возможных последовательностей перестановок, тогда как существует только n ! возможные перестановки массива из n элементов. Поскольку n n никогда не может делиться на n без остатка ! когда n > 2 (поскольку последний делится на n −1, который не имеет общих простых делителей с n ), некоторые перестановки должны быть произведены с помощью большего количества n n последовательностей перестановок, чем другие. В качестве конкретного примера этой предвзятости рассмотрим распределение возможных результатов перетасовки трехэлементного массива [1, 2, 3]. Существует 6 возможных перестановок этого массива (3! = 6), но алгоритм производит 27 возможных перетасовок (3 3 = 27). В этом случае [1, 2, 3], [3, 1, 2] и [3, 2, 1] каждая получается в результате 4 из 27 тасовок, а каждая из оставшихся 3 перестановок происходит в 5 из 27 перестановок. шаркает.
Матрица справа показывает вероятность того, что каждый элемент списка длиной 7 окажется в любой другой позиции. Обратите внимание, что для большинства элементов попадание в исходное положение (основную диагональ матрицы) имеет наименьшую вероятность, а перемещение на один слот назад имеет наибольшую вероятность.
Перетасовка Фишера-Йейтса предполагает выбор равномерно распределенных случайных целых чисел из различных диапазонов. Однако большинство генераторов случайных чисел — как истинных, так и псевдослучайных — напрямую предоставляют числа только в фиксированном диапазоне от 0 до RAND_MAX, а в некоторых библиотеках RAND_MAX может составлять всего 32767. [15] Простой и часто используемый способ принудительного вычисления. такие числа в желаемый диапазон — применить оператор по модулю ; то есть разделить их на размер диапазона и взять остаток. Однако необходимость в перетасовке Фишера-Йейтса генерировать случайные числа в каждом диапазоне от 0–1 до 0– n почти гарантирует, что некоторые из этих диапазонов не будут равномерно разделять естественный диапазон генератора случайных чисел. Таким образом, остатки не всегда будут распределяться равномерно, и, что еще хуже, систематическая ошибка будет в пользу небольших остатков.
Например, предположим, что ваш источник случайных чисел дает числа от 0 до 99 (как это было в случае с исходными таблицами Фишера и Йейтса), и что вы хотите получить несмещенное случайное число от 0 до 15. Если вы просто разделите числа на 16 и возьмите остаток, вы обнаружите, что числа 0–3 встречаются примерно на 17% чаще, чем другие. Это связано с тем, что 16 не делит 100 поровну: наибольшее кратное 16, меньшее или равное 100, составляет 6 × 16 = 96, и именно числа в неполном диапазоне 96–99 вызывают смещение. Самый простой способ решить проблему — отбросить эти числа, прежде чем брать остаток, и продолжать попытки снова, пока не появится число в подходящем диапазоне. Хотя в принципе это может, в худшем случае, занять вечность, ожидаемое количество повторных попыток всегда будет меньше одной.
Схожая проблема возникает с реализациями, которые сначала генерируют случайное число с плавающей запятой — обычно в диапазоне [0,1] — а затем умножают его на размер желаемого диапазона и округляют в меньшую сторону. Проблема здесь в том, что случайные числа с плавающей запятой, как бы тщательно они ни генерировались, всегда имеют лишь конечную точность. Это означает, что в любом заданном диапазоне существует только конечное число возможных значений с плавающей запятой, и если диапазон разделить на несколько сегментов, которые не делят это число поровну, в некоторых сегментах будет больше возможных значений, чем в других. Хотя результирующее смещение не будет демонстрировать такую же систематическую тенденцию к снижению, как в предыдущем случае, оно все равно будет присутствовать.
Дополнительная проблема возникает, когда тасование Фишера-Йейтса используется с генератором псевдослучайных чисел или ГПСЧ: поскольку последовательность чисел, выводимых таким генератором, полностью определяется его внутренним состоянием в начале последовательности, тасование, вызванное таким Генератор не может создать больше различных перестановок, чем количество различных возможных состояний генератора. [16] Даже когда количество возможных состояний превышает количество перестановок, нерегулярный характер отображения последовательностей чисел в перестановки означает, что некоторые перестановки будут происходить чаще, чем другие. Таким образом, чтобы минимизировать погрешность, количество состояний ГПСЧ должно превышать количество перестановок как минимум на несколько порядков.
Например, встроенный генератор псевдослучайных чисел, предоставляемый многими языками программирования и/или библиотеками, часто может иметь только 32 бита внутреннего состояния, что означает, что он может генерировать только 2–32 различных последовательностей чисел. Если такой генератор использовать для перетасовки колоды из 52 игральных карт , он сможет произвести лишь очень небольшую часть из 52! ≈ 2 225,6 возможных перестановок. Генератор с внутренним состоянием менее 226 бит не может создать все возможные перестановки колоды из 52 карт.
Ни один генератор псевдослучайных чисел не может создавать более различные последовательности, начиная с точки инициализации, чем существуют различные начальные значения, которыми он может быть инициализирован. Таким образом, генератор, имеющий 1024 бита внутреннего состояния, но инициализируемый 32-битным начальным числом, может по-прежнему производить только 2 32 различных перестановки сразу после инициализации. Он может произвести больше перестановок, если использовать генератор очень много раз, прежде чем начать использовать его для генерации перестановок, но это очень неэффективный способ увеличения случайности: предположим, что можно организовать использование генератора случайных чисел до миллиарда. , скажем, 2 30 для простоты, время между инициализацией и генерацией перестановок, тогда количество возможных перестановок все равно будет всего 2 62 .
Еще одна проблема возникает, когда простой линейный конгруэнтный ГПСЧ используется с описанным выше методом сокращения диапазона «раздели и возьми остаток». Проблема здесь в том, что младшие биты линейного конгруэнтного ГПСЧ с модулем 2 e менее случайны, чем старшие: [6] сами младшие n бит генератора имеют период не более 2 n . Когда делитель представляет собой степень двойки, взятие остатка, по сути, означает отбрасывание старших битов, в результате чего получается значительно меньшее случайное значение. Если LCG имеет простое число по модулю, применяются другие правила, но такие генераторы встречаются редко. Это пример общего правила, согласно которому некачественный ГСЧ или ГПСЧ приводит к некачественным перетасовкам.