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

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

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

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

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

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

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

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

Современная версия тасования Фишера – Йейтса, предназначенная для использования на компьютере, была представлена Ричард Дюрстенфельд в 1964 г.^[2] и популяризируется Дональд Э. Кнут в Искусство программирования как «Алгоритм P (Перемешивание)».^[3] Ни статья Дюрстенфельда, ни первое издание книги Кнута. Искусство программирования высоко оценил работу Фишера и Йейтса; они могли не знать об этом. Последующие издания Knuth's Искусство программирования упомянуть вклад Фишера и Йейтса.^[4]

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

- Перетасовать массив а из п элементы (индексы 0 ..п-1):за я из п−1 вниз 1 делать     j ← случайное целое число такое, что 0 ≤ j ≤ я     обмен а[j] и а[я]

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

- Перетасовать массив а из п элементы (индексы 0 ..п-1):за я из 0 к п−1 делать     j ← случайное целое число такое, что я ≤ j < п     обмен а[я] и а[j]

Примеры

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

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

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

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

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

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

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

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

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

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

На этом этапе больше ничего нельзя сделать, поэтому в результате получается перестановка 7 5 4 3 1 8 2 6.

Варианты

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

Эта секция возможно содержит оригинальные исследования. Пожалуйста Улучши это к проверка заявленные претензии и добавление встроенные цитаты. Заявления, содержащие только оригинальные исследования, следует удалить. (Апрель 2017 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

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

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

Чтобы инициализировать массив а из п элементы в случайно перемешанную копию источник, оба на основе 0: за я из 0 к п − 1 делать      j ← случайное целое число такое, что 0 ≤ j ≤ я      если j ≠ я          а[я] ← а[j]      а[j] ← источник[я]

Перемешивание наизнанку можно увидеть по индукция. Предполагая идеальный генератор случайных чисел, каждый из п! различные последовательности случайных чисел, которые можно было получить из вызовов случайный приведет к другой перестановке значений, поэтому все они будут получены ровно один раз. Условие, которое проверяет, если j ≠ я может быть опущено на языках, в которых нет проблем с доступом к неинициализированным значениям массива. Это устраняет п условные переходы за счет ЧАС_п ≈ пер п + γ избыточные задания.

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

Чтобы инициализировать пустой массив а на случайно перемешанную копию источник длина которых неизвестна: пока источник.moreDataAvailable j ← случайное целое число такое, что 0 ≤ j ≤ а.длина если j = а.длина а.append (источник.следующий) еще          а.append (а[j])          а[j] ← источник.следующий

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

Очень похожий алгоритм был опубликован в 1986 г. Сандра Саттоло для создания равномерно распределенных циклы (максимальной) длины п.^[6][7] Единственное различие между алгоритмами Дюрстенфельда и Саттоло состоит в том, что в последнем, на шаге 2 выше, случайное число j выбирается из диапазона от 1 до я−1 (а не между 1 и я) включительно. Это простое изменение модифицирует алгоритм так, что результирующая перестановка всегда состоит из одного цикла.

Фактически, как описано ниже, довольно легко случайно реализовать алгоритм Саттоло, когда предполагается обычное перемешивание Фишера – Йетса. Это приведет к смещению результатов, заставляя перестановки выбираться из меньшего набора (п−1)! циклы длины N, а не из полного набора всех п! возможные перестановки.

Тот факт, что алгоритм Саттоло всегда производит цикл длины п может быть показано индукция. Предположим по индукции, что после начальной итерации цикла оставшиеся итерации переставляют первую п - 1 элемент по циклу длины п - 1 (оставшиеся итерации - это всего лишь алгоритм Саттоло, примененный к первым п - 1 элемент). Это означает, что отслеживание исходного элемента до его новой позиции п, то элемент изначально в позиции п в новое положение и т.д., можно вернуться в исходное положение только после посещения всех остальных позиций. Предположим, что начальная итерация поменяла местами последний элемент с элементом в (не конечной) позиции k, и что последующая перестановка первых п - 1 элемент затем переместил его на позициюл; мы сравниваем перестановкуπ из всех п элементы с этой оставшейся перестановкойσ из первых п - 1 элемент. При отслеживании последовательных позиций, как уже упоминалось, нет разницы между π и σ до прибытия на позициюk. Но тогда подπ элемент изначально в позицииk перемещается в конечную позицию, а не в позициюл, а элемент, изначально находящийся в последней позиции, перемещается в позициюл. С этого момента последовательность позиций дляπ снова следует последовательности дляσ, и все позиции будут посещены, прежде чем вернуться в исходное положение, если потребуется.

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

Пример реализации алгоритма Саттоло в Python является:

из случайный импорт Randrangedef sattolo_cycle(Предметы) -> Никто:    "" "Алгоритм Саттоло." ""    я = len(Предметы)    пока я > 1:        я = я - 1        j = Randrange(я)  # 0 <= j <= i-1        Предметы[j], Предметы[я] = Предметы[я], Предметы[j]

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

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

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

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

из случайный импорт Randrangedef naive_shuffle(Предметы) -> Никто:    "" "Наивный метод. Это пример того, чего нельзя делать - используйте вместо этого Фишера-Йейтса." ""    п = len(Предметы)    за я в классифицировать(п):        j = Randrange(п)  # 0 <= j <= n-1        Предметы[j], Предметы[я] = Предметы[я], Предметы[j]

Сортировка

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

Вариант вышеупомянутого метода, который нашел некоторое применение в языках, поддерживающих сортировку с указанными пользователем функциями сравнения, - это перемешивание списка путем его сортировки с помощью функции сравнения, которая возвращает случайные значения. Тем не мение, это очень плохой метод: очень вероятно, что будут получены сильно неоднородные распределения, что, кроме того, сильно зависит от используемого алгоритма сортировки.^[10][11]Например, предположим быстрая сортировка используется как алгоритм сортировки с фиксированным элементом, выбранным первым поворотный элемент. Запускается алгоритм сравнения стержня со всеми другими элементами, чтобы отделить их в те меньше и тем больше, чем это, и относительных размерах этих групп будут определять окончательное место элемента поворота. Для равномерно распределенного случайная перестановка, Каждое возможное конечное положение должно быть с равной вероятностью для элемента поворота, но если каждый из начальных сравнений возвращают «меньше» или «больше» с равной вероятностью, то, что позиция будет иметь биномиальное распределение за п = 1/2, что дает позиции около середины последовательности с гораздо большей вероятностью, чем позиции около концов. Функции рандомизированного сравнения, применяемые к другим методам сортировки, таким как Сортировка слиянием может давать результаты, которые кажутся более однородными, но не совсем так, поскольку объединение двух последовательностей путем многократного выбора одной из них с равной вероятностью (до тех пор, пока выбор не будет вызван исчерпанием одной последовательности), не дает результатов с равномерным распределением; вместо этого вероятность выбрать последовательность должна быть пропорциональна количеству оставшихся в ней элементов.^{[нужна цитата ]}. Фактически нет метода, который использует только двусторонние случайные события с равной вероятностью ("подбрасывание монеты" ), повторяемый ограниченное количество раз, может производить перестановки последовательности (более двух элементов) с равномерным распределением, потому что каждый путь выполнения будет иметь в качестве вероятности рациональное число со знаменателем степень 2, а искомая вероятность 1 /п! для каждой возможной перестановки не такой формы^{[нужна цитата ]}.

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

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

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

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

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

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

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

Точно так же всегда выбирая j из всего диапазона допустимых индексов массива на каждый итерация также дает результат, который является необъективным, хотя и менее очевидным. Это видно из того факта, что это дает п^п различные возможные последовательности свопов, тогда как есть только п! возможные перестановки п-элементный массив. С п^п никогда не может делиться без остатка на п! когда п > 2 (так как последнее делится на п−1, который не имеет главные факторы с п), некоторые перестановки должны производиться большей частью п^п последовательности свопов, чем другие. В качестве конкретного примера такого предубеждения рассмотрим распределение возможных результатов перетасовки трехэлементного массива [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.^[13] Простой и обычно используемый способ принудительно установить такие числа в желаемый диапазон - это применить оператор по модулю; то есть разделить их на размер диапазона и взять остаток. Однако необходимость перемешивания Фишера – Йейтса для генерации случайных чисел в каждом диапазоне от 0–1 до 0–п в значительной степени гарантирует, что некоторые из этих диапазонов не будут равномерно делить естественный диапазон генератора случайных чисел. Таким образом, остатки не всегда будут распределяться равномерно и, что еще хуже, систематическое смещение будет в пользу небольших остатков.

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

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

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

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

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

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

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

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

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

Рекомендации

внешняя ссылка

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