Тасование Фишера – Йетса - Fisher–Yates shuffle

Пример перетасовки девяти букв с помощью перетасовки Фишера – Йейтса, созданной Дарстенфельдом на месте

Перетасовка Фишера-Йейтс представляет собой алгоритм для генерации случайных перестановок конечной последовательности -в обиняков, алгоритм перемешивает последовательность. Алгоритм эффективно складывает все элементы в шляпу; он постоянно определяет следующий элемент, случайным образом вытягивая элемент из шляпы, пока не останется никаких элементов. Алгоритм производит беспристрастную перестановку: каждая перестановка одинаково вероятна. Современная версия алгоритма эффективна: требуется время, пропорциональное количеству перемешиваемых элементов, и перемешивание их на месте .

Перетасовка Фишера – Йейтса названа в честь Рональда Фишера и Фрэнка Йейтса , которые впервые ее описали, и также известна как перетасовка Кнута в честь Дональда Кнута . Вариант тасования Фишера – Йейтса, известный как алгоритм Саттоло , может использоваться для генерации случайных циклических перестановок длины n вместо случайных перестановок.

Оригинальный метод Фишера и Йейтса

Перетасовка Фишера – Йетса в ее первоначальном виде была описана в 1938 году Рональдом Фишером и Фрэнком Йейтсом в их книге « Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований» . В их описании алгоритма использовались карандаш и бумага; таблица случайных чисел обеспечила случайность. Базовый метод для генерации случайной перестановки чисел от 1 до N выглядит следующим образом:

1. Запишите число от 1 до N .
2. Выберите случайное число k между единицей и количеством оставшихся незачеркнутых чисел (включительно).
3. Считая с нижнего конца, вычеркните k- е число, которое еще не вычеркнуто, и запишите его в конце отдельного списка.
4. Повторите действия, начиная с шага 2, пока все числа не будут вычеркнуты.
5. Последовательность чисел, записанная на шаге 3, теперь представляет собой случайную перестановку исходных чисел.

При условии, что случайные числа, выбранные на шаге 2 выше, действительно случайны и беспристрастны, то же самое будет и с результирующей перестановкой. Фишер и Йейтс постарались описать, как получить такие случайные числа в любом желаемом диапазоне из предоставленных таблиц таким образом, чтобы избежать какой-либо систематической ошибки. Они также предложили возможность использования более простого метода - выбор случайных чисел от 1 до N и отбрасывание любых дубликатов - для генерации первой половины перестановки и применение более сложного алгоритма только к оставшейся половине, где выбор повторяющегося числа будет в противном случае стать удручающе обычным явлением.

Современный алгоритм

Современная версия перемешивания Фишера – Йейтса, разработанная для использования на компьютере, была представлена Ричардом Дюрстенфельдом в 1964 году и популяризирована Дональдом Э. Кнутом в книге «Искусство компьютерного программирования» как «Алгоритм P (перемешивание)». Ни статья Дюрстенфельда, ни первое издание книги Кнута « Искусство компьютерного программирования» не признают работу Фишера и Йейтса; они могли не знать об этом. В последующих выпусках книги Кнута « Искусство компьютерного программирования» упоминается вклад Фишера и Йейтса.

Алгоритм, описанный Дюрстенфельдом, немного отличается от алгоритма, предложенного Фишером и Йейтсом. В то время как наивная компьютерная реализация метода Фишера и Йейтса потратила бы ненужное время на подсчет оставшихся чисел на шаге 3 выше, решение Дюрстенфельда состоит в том, чтобы переместить «пораженные» числа в конец списка, заменяя их последним незаметным числом на каждом итерация. Это снижает временную сложность алгоритма до , по сравнению с наивной реализацией. Это изменение дает следующий алгоритм (для массива с нулевым отсчетом ). ${\ Displaystyle {\ mathcal {O}} (п)}$${\ Displaystyle {\ mathcal {O}} (п ^ {2})}$

-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

Эквивалентная версия, которая перетасовывает массив в противоположном направлении (от самого низкого индекса до самого высокого):

-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

Примеры

Карандашно-бумажный метод

В качестве примера мы переставим буквы от A до H, используя оригинальный метод Фишера и Йейтса . Начнем с написания букв на листе бумаги для заметок:

Теперь мы набираем случайное число k от 1 до 8 - давайте сделаем это 3 - и вычеркиваем k- ю (т.е. третью) букву в блокноте и записываем ее как результат:

Теперь мы выбираем второе случайное число, на этот раз от 1 до 7: оказывается, что это 4. Теперь мы вычеркиваем четвертую букву, еще не вычеркнутую из блокнота - это буква E - и добавляем ее к результату:

Теперь мы выбираем следующее случайное число от 1 до 6, а затем от 1 до 5 и так далее, всегда повторяя процесс вычеркивания, как указано выше:

Современный метод

Теперь мы сделаем то же самое, используя версию алгоритма Дюрстенфельда : на этот раз вместо того, чтобы вычеркивать выбранные буквы и копировать их в другом месте, мы поменяем их местами с последней, еще не выбранной буквой. Начнем с написания букв от A до H, как и раньше:

Для нашего первого броска мы выбираем случайное число от 1 до 8: на этот раз это 6, поэтому мы меняем местами 6-ю и 8-ю буквы в списке:

Следующее случайное число, которое мы выбираем от 1 до 7, оказывается 2. Таким образом, мы меняем местами 2-ю и 7-ю буквы и идем дальше:

Следующее случайное число, которое мы выбрасываем, - от 1 до 6, и оказалось, что оно равно 6, что означает, что мы оставляем 6-ю букву в списке (которая после перестановки выше теперь буква H) на месте и просто переходим к следующей. шаг. Снова действуем так же, пока перестановка не будет завершена:

На этом этапе больше ничего нельзя сделать, поэтому в результате получается перестановка GEDCAHB F.

Варианты

Алгоритм "наизнанку"

Перемешивание Фишера – Йетса, реализованное Дюрстенфельдом, - это перемешивание на месте . То есть, учитывая предварительно инициализированный массив, он перемешивает элементы массива на месте, а не создает перемешанную копию массива. Это может быть преимуществом, если перетасовываемый массив большой.

Чтобы одновременно инициализировать и перемешать массив, можно добиться большей эффективности, выполнив «перевернутую» версию перемешивания. В этой версии один последовательно помещает элемент номер i в случайную позицию среди первых i позиций в массиве после перемещения элемента, ранее занимавшего эту позицию, в позицию i . В случае, если случайной позицией является номер i , этот «ход» (в то же место) включает неинициализированное значение, но это не имеет значения, поскольку значение затем немедленно перезаписывается. Никакой отдельной инициализации не требуется, и обмен не производится. В общем случае, когда источник определяется некоторой простой функцией, такой как целые числа от 0 до n  - 1, источник можно просто заменить функцией, поскольку источник никогда не изменяется во время выполнения.

To initialize an array a of n elements to a randomly shuffled copy of source, both 0-based:
  for i from 0 to n − 1 do
      j ← random integer such that 0 ≤ j ≤ i
      if j ≠ i
          a[i] ← a[j]
      a[j] ← source[i]

Перемешивание наизнанку можно увидеть по индукции . Предполагая идеальный генератор случайных чисел, каждый из n ! разные последовательности случайных чисел, которые могут быть получены из вызовов random, будут производить различную перестановку значений, поэтому все они получаются ровно один раз. Условие, которое проверяет, может ли j ≠ i быть опущено в языках, у которых нет проблем с доступом к неинициализированным значениям массива. Это устраняет n условных переходов за счет избыточных назначений H _n ≈ ln n + γ .

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

To initialize an empty array a to a randomly shuffled copy of source whose length is not known:
  while source.moreDataAvailable
      j ← random integer such that 0 ≤ j ≤ a.length
      if j = a.length
          a.append(source.next)
      else
          a.append(a[j])
          a[j] ← source.next

Алгоритм Саттоло

Очень похожий алгоритм был опубликован в 1986 году Сандрой Саттоло для генерации равномерно распределенных циклов (максимальной) длины n . Единственное различие между алгоритмами Дюрстенфельда и Саттоло состоит в том, что в последнем, на шаге 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 :

from random import randrange

def sattolo_cycle(items) -> None:
    """Sattolo's algorithm."""
    i = len(items)
    while i > 1:
        i = i - 1
        j = randrange(i)  # 0 <= j <= i-1
        items[j], items[i] = items[i], items[j]

Сравнение с другими алгоритмами перетасовки

Асимптотическая временная и пространственная сложность перетасовки Фишера – Йейтса оптимальна. В сочетании с высококачественным источником непредвзятых случайных чисел это также гарантирует получение объективных результатов. По сравнению с некоторыми другими решениями, это также имеет то преимущество, что, если требуется только часть результирующей перестановки, ее можно остановить на полпути или даже останавливать и перезапускать повторно, генерируя перестановку постепенно по мере необходимости.

Наивный метод

Наивный метод замены каждого элемента другим элементом, выбранным случайным образом из всех элементов, является необъективным и в корне неверным. Различные перестановки будут иметь разные вероятности генерируются для каждого , так как число различных перестановок , не равномерно разделить количество случайных результатов алгоритма . В частности, согласно постулату Бертрана между и будет хотя бы одно простое число , и это число будет делить, но не делить . ${\ displaystyle n> 2}$${\ displaystyle n!}$${\ Displaystyle п ^ {п}}$${\ displaystyle n / 2}$${\ displaystyle n}$${\ displaystyle n!}$${\ Displaystyle п ^ {п}}$

from random import randrange

def naive_shuffle(items) -> None:
    """A naive method. This is an example of what not to do -- use Fisher-Yates instead."""
    n = len(items)
    for i in range(n):
        j = randrange(n)  # 0 <= j <= n-1
        items[j], items[i] = items[i], items[j]

Сортировка

Альтернативный метод присваивает случайный номер каждому элементу перетасовываемого набора, а затем сортирует набор в соответствии с назначенными номерами. Метод сортировки имеет ту же асимптотическую временную сложность, что и метод Фишера – Йейтса: хотя общая сортировка составляет O ( n  log  n ), числа эффективно сортируются с использованием сортировки Radix за время O ( n ). Подобно перетасовке Фишера – Йейтса, метод сортировки дает объективные результаты. Однако необходимо следить за тем, чтобы назначенные случайные числа никогда не дублировались, поскольку алгоритмы сортировки обычно не упорядочивают элементы случайным образом в случае ничьей. Кроме того, этот метод требует асимптотически большего пространства: O ( n ) дополнительного места для хранения случайных чисел по сравнению с O (1) для перемешивания Фишера – Йейтса. Наконец, отметим, что метод сортировки имеет простую параллельную реализацию, в отличие от тасования Фишера – Йейтса, которое является последовательным.

Вариант вышеупомянутого метода, который нашел некоторое применение в языках, поддерживающих сортировку с указанными пользователем функциями сравнения, - это перемешивание списка путем его сортировки с помощью функции сравнения, которая возвращает случайные значения. Однако это крайне плохой метод : он с большой вероятностью приведет к сильно неравномерному распределению, что, кроме того, сильно зависит от используемого алгоритма сортировки. Например, предположим, что в качестве алгоритма сортировки используется быстрая сортировка с фиксированным элементом, выбранным в качестве первого элемента поворота . Алгоритм начинает сравнение опорной точки со всеми другими элементами, чтобы разделить их на меньшие и большие, и относительные размеры этих групп определят окончательное место опорного элемента. Для равномерно распределенной случайной перестановки каждая возможная конечная позиция должна быть одинаково вероятной для опорного элемента, но если каждое из начальных сравнений возвращает «меньше» или «больше» с равной вероятностью, тогда эта позиция будет иметь биномиальное распределение для p  = 1/2, что дает позиции около середины последовательности с гораздо большей вероятностью, чем позиции около концов. Функции рандомизированного сравнения, применяемые к другим методам сортировки, таким как сортировка слиянием, могут давать результаты, которые кажутся более однородными, но это тоже не совсем так, поскольку слияние двух последовательностей путем многократного выбора одной из них с равной вероятностью (до тех пор, пока выбор не будет вызван исчерпанием одной из них). последовательность) не дает результатов с равномерным распределением; вместо этого вероятность выбрать последовательность должна быть пропорциональна количеству оставшихся в ней элементов. Фактически, ни один метод, который использует только двусторонние случайные события с равной вероятностью ( «подбрасывание монеты» ), повторяющиеся ограниченное количество раз, не может производить перестановки последовательности (более двух элементов) с равномерным распределением, потому что каждое выполнение путь будет иметь в качестве вероятности рациональное число со степенью 2 в знаменателе , в то время как требуемая вероятность 1 / n ! для каждой возможной перестановки не такой формы.

В принципе, этот метод перетасовки может даже привести к ошибкам программы, таким как бесконечные циклы или нарушения доступа, потому что правильность алгоритма сортировки может зависеть от свойств отношения порядка (например, транзитивности ), которых при сравнении, производящем случайные значения, определенно не будет. Хотя такого рода поведение не должно происходить с процедурами сортировки, которые никогда не выполняют сравнение, результат которого может быть предсказан с уверенностью (на основе предыдущих сравнений), могут быть веские причины для преднамеренного проведения таких сравнений. Например, тот факт, что любой элемент должен сравниваться с самим собой, позволяет использовать их в качестве контрольных значений по соображениям эффективности, и в этом случае функция случайного сравнения нарушит алгоритм сортировки.

Возможные источники предвзятости

При реализации тасования Фишера – Йейтса необходимо соблюдать осторожность, как при реализации самого алгоритма, так и при генерации случайных чисел, на которых он построен, в противном случае результаты могут показать заметную погрешность. Ниже перечислен ряд распространенных источников предвзятости.

Ошибки реализации

Распространенной ошибкой при реализации тасования Фишера – Йейтса является выбор случайных чисел из неправильного диапазона. Может показаться, что ошибочный алгоритм работает правильно, но он не будет производить каждую возможную перестановку с равной вероятностью, и он может вообще не произвести определенные перестановки. Например, распространенной ошибкой при замене на единицу будет выбор индекса j записи для обмена в приведенном выше примере так, чтобы он всегда был строго меньше индекса i записи, с которой она будет заменена. Это превращает перемешивание Фишера – Йейтса в алгоритм Саттоло , который производит только перестановки, состоящие из одного цикла, включающего все элементы: в частности, с этой модификацией ни один элемент массива никогда не может оказаться в исходном положении.

Предвзятость заказа из-за неправильной реализации

Смещение заказа из-за неправильной реализации - n = 1000

Точно так же всегда выбор j из всего диапазона допустимых индексов массива на каждой итерации также дает результат, который является смещенным, хотя и менее очевидным. Это видно из того факта, что это дает n ⁿ различных возможных последовательностей обмена, тогда как их всего n ! возможные перестановки n -элементного массива. Поскольку n ⁿ никогда не может делиться на n без остатка ! когда n > 2 (поскольку последний делится на n −1, который не имеет делителей простых делителей с n ), некоторые перестановки должны производиться большим количеством из n ⁿ последовательностей перестановок, чем другие. В качестве конкретного примера такого предубеждения рассмотрим распределение возможных результатов перетасовки трехэлементного массива [1, 2, 3]. Есть 6 возможных перестановок этого массива (3! = 6), но алгоритм производит 27 возможных перестановок (3 ³ = 27). В этом случае [1, 2, 3], [3, 1, 2] и [3, 2, 1] являются результатом 4 из 27 перетасовок, в то время как каждая из оставшихся 3 перестановок происходит в 5 из 27 тасует.

Матрица справа показывает вероятность того, что каждый элемент в списке длиной 7 окажется в любой другой позиции. Обратите внимание, что для большинства элементов попадание в исходное положение (главная диагональ матрицы) имеет наименьшую вероятность, а перемещение на один слот назад имеет наибольшую вероятность.

Смещение по модулю

Перемешивание Фишера – Йетса включает выбор равномерно распределенных случайных целых чисел из различных диапазонов. Однако большинство генераторов случайных чисел - истинных или псевдослучайных - будут напрямую предоставлять числа только в фиксированном диапазоне от 0 до RAND_MAX, а в некоторых библиотеках RAND_MAX может быть всего лишь 32767. Простой и часто используемый способ принудительно ввести такие числа в желаемый диапазон - применить оператор по модулю ; то есть разделить их на размер диапазона и взять остаток. Однако необходимость тасования Фишера – Йейтса для генерации случайных чисел в каждом диапазоне от 0–1 до 0– n почти гарантирует, что некоторые из этих диапазонов не будут равномерно делить естественный диапазон генератора случайных чисел. Таким образом, остатки не всегда будут распределяться равномерно и, что еще хуже, систематическая ошибка будет систематически в пользу небольших остатков.

Например, предположим, что ваш источник случайных чисел дает числа от 0 до 99 (как это было в случае с исходными таблицами Фишера и Йейтса), и что вы хотите получить несмещенное случайное число от 0 до 15. Если вы просто разделите числа умножив на 16 и возьмите остаток, вы обнаружите, что числа 0–3 встречаются примерно на 17% чаще, чем другие. Это связано с тем, что число 16 не делит 100 поровну: наибольшее кратное 16, меньшее или равное 100, составляет 6 × 16 = 96, а смещение вызывают числа в неполном диапазоне 96–99. Самый простой способ решить проблему - отбросить эти числа, прежде чем брать остаток, и продолжать попытки до тех пор, пока не появится число из подходящего диапазона. Хотя в принципе это может занять в худшем случае вечность, ожидаемое количество повторных попыток всегда будет меньше единицы.

Связанная проблема возникает с реализациями, которые сначала генерируют случайное число с плавающей запятой - обычно в диапазоне [0,1] - а затем умножают его на размер желаемого диапазона и округляют в меньшую сторону. Проблема здесь в том, что случайные числа с плавающей запятой, как бы тщательно они ни создавались, всегда имеют только конечную точность. Это означает, что существует только конечное число возможных значений с плавающей запятой в любом заданном диапазоне, и если диапазон разделен на несколько сегментов, которые не делят это число равномерно, в некоторых сегментах будет больше возможных значений, чем в других. . Хотя результирующее смещение не будет иметь такой же систематический нисходящий тренд, как в предыдущем случае, оно все равно будет.

Псевдослучайные генераторы

Дополнительная проблема возникает, когда тасование Фишера-Йейтса используется с генератором псевдослучайных чисел или ГПСЧ: поскольку последовательность чисел, выводимая таким генератором, полностью определяется его внутренним состоянием в начале последовательности, тасование, управляемое таким генератором генератор не может производить более различных перестановок, чем генератор имеет различные возможные состояния. Даже когда количество возможных состояний превышает количество перестановок, нерегулярный характер отображения последовательностей чисел на перестановки означает, что одни перестановки будут происходить чаще, чем другие. Таким образом, чтобы минимизировать смещение, количество состояний ГПСЧ должно превышать количество перестановок по крайней мере на несколько порядков.

Например, встроенный генератор псевдослучайных чисел, предоставляемый многими языками программирования и / или библиотеками, часто может иметь только 32 бита внутреннего состояния, что означает, что он может создавать только 2 ³² различных последовательности чисел. Если такой генератор используется для перетасовки колоды из 52 игральных карт , он может произвести лишь очень небольшую часть из 52! ≈ ^2225,6 возможных перестановок. Генератор с менее чем 226 битами внутреннего состояния не может произвести все возможные перестановки колоды из 52 карт.

Никакой генератор псевдослучайных чисел не может создавать более различных последовательностей, начиная с точки инициализации, чем есть различные начальные значения, которыми он может быть инициализирован. Таким образом, генератор, имеющий 1024 бита внутреннего состояния, но инициализированный 32-битным начальным числом, может по-прежнему производить только 2 ³² различных перестановки сразу после инициализации. Он может произвести больше перестановок, если многократно задействовать генератор перед тем, как начать использовать его для генерации перестановок, но это очень неэффективный способ увеличения случайности: предположим, можно организовать использование генератора случайного числа до миллиарда. скажем, 2 ³⁰ для простоты, раз между инициализацией и генерацией перестановок, то количество возможных перестановок по-прежнему будет только 2 ⁶² .

Еще одна проблема возникает, когда простой линейный конгруэнтный ГПСЧ используется с описанным выше методом деления и извлечения остатка для уменьшения диапазона. Проблема здесь в том, что младшие биты линейного конгруэнтного ГПСЧ с модулем 2 ^e менее случайны, чем биты высокого порядка: младшие n битов самого генератора имеют период не более 2 ⁿ . Когда делитель представляет собой степень двойки, получение остатка по существу означает отбрасывание старших битов, так что в итоге получается значительно меньшее случайное значение. Если в LCG есть простой модуль по модулю, применяются другие правила , но такие генераторы встречаются редко. Это пример общего правила, согласно которому некачественный ГСЧ или ГПСЧ приведет к некачественному перемешиванию.

Смотрите также

• RC4 , потоковый шифр, основанный на перетасовке массива
• Отбор проб из коллектора , в частности алгоритм R, который является специализацией метода перетасовки Фишера – Йейтса.

использованная литература

внешние ссылки

• Интерактивный пример