Перетасовка Фишера-Йейтса
Перетасовка Фишера -Йейтса это алгоритм перетасовки — конечной последовательности . Алгоритм берет список всех элементов последовательности и постоянно определяет следующий элемент в перетасованной последовательности, случайным образом извлекая элемент из списка до тех пор, пока элементов не останется. [1] Алгоритм создает несмещенную перестановку: каждая перестановка одинаково вероятна. Современная версия алгоритма требует времени, пропорционального количеству перетасовываемых предметов, и перетасовывает их на месте .
Тасовка Фишера-Йейтса названа в честь Рональда Фишера и Фрэнка Йейтса , которые впервые ее описали. Это также известно как перетасовка Кнута в честь Дональда Кнута . [2] Вариант перетасовки Фишера-Йейтса, известный как алгоритм Саттоло , может использоваться для генерации случайных циклических перестановок длины n вместо случайных перестановок.
Фишера и Оригинальный Йейтса метод
Тасовка Фишера-Йейтса в своей первоначальной форме была описана в 1938 году Рональдом Фишером и Фрэнком Йейтсом в их книге «Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований» . [3] В описании алгоритма использовались карандаш и бумага; таблица случайных чисел обеспечивала случайность. Основной метод генерации случайной перестановки чисел от 1 до N заключается в следующем:
- Запишите числа от 1 N. до
- Выберите случайное число k между единицей и количеством оставшихся невычеркнутых чисел (включительно).
- Считая с нижнего конца, вычеркните еще не вычеркнутое k -е число и запишите его в конце отдельного списка.
- Повторяйте, начиная с шага 2, пока все цифры не будут вычеркнуты.
- Последовательность чисел, записанная на шаге 3, теперь представляет собой случайную перестановку исходных чисел.
При условии, что случайные числа, выбранные на шаге 2 выше, действительно случайны и несмещены, такой же будет и результирующая перестановка. Фишер и Йейтс постарались описать, как получить такие случайные числа в любом желаемом диапазоне из предоставленных таблиц таким образом, чтобы избежать какой-либо предвзятости. Они также предложили возможность использовать более простой метод — выбор случайных чисел от одного до N и отбрасывание всех дубликатов — для создания первой половины перестановки и применение более сложного алгоритма только к оставшейся половине, где выбор повторяющегося числа приведет к в противном случае они станут удручающе обычным явлением.
Современный алгоритм [ править ]
Современная версия перетасовки Фишера-Йейтса, разработанная для использования на компьютере, была представлена Ричардом Дерстенфельдом в 1964 году. [4] и популяризирован Дональдом Э. Кнутом в книге «Искусство компьютерного программирования» как «Алгоритм P (перетасовка)». [5] Ни в статье Дюрстенфельда, ни в первом издании Кнута «Искусство компьютерного программирования» не были признаны работы Фишера и Йейтса; они, возможно, не знали об этом. [ нужна ссылка ] В последующих изданиях книги Кнута « Искусство компьютерного программирования» упоминается вклад Фишера и Йейтса. [6]
Алгоритм, описанный Дюрстенфельдом, более эффективен, чем алгоритм, предложенный Фишером и Йейтсом: в то время как наивная компьютерная реализация метода Фишера и Йейтса потребовала бы лишней траты времени на подсчет оставшихся чисел на шаге 3 выше, решение Дюрстенфельда состоит в том, чтобы переместить «выбранные» числа. в конец списка, заменяя их последним невычеркнутым номером на каждой итерации. алгоритма Это уменьшает временную сложность до по сравнению с для наивной реализации. [7] Это изменение дает следующий алгоритм (для с нулевым индексом массива ).
-- To shuffle an array a of n elements (indices 0..n-1):
for i from n−1 down to 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 переставляются с использованием оригинального метода Фишера и Йейтса, начиная с букв в алфавитном порядке:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| ABCDEFGH |
случайное число j Выбирается от 1 до 8. Если , например, j =3, то в блокноте вычеркивают третью букву и записывают ее как результат:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| 1–8 | 3 | АБ |
С |
Выбирается второе случайное число, на этот раз от 1 до 7. Если число равно 4, то вычеркивают еще не вычеркнутую из блокнота четвертую букву и прибавляют ее к результату:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| 1–7 | 4 | AB |
ЕСТЬ |
Следующее случайное число выбирается от 1 до 6, затем от 1 до 5 и так далее, всегда повторяя процесс вычеркивания, как указано выше:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| 1–6 | 5 | AB |
СЕ Г |
| 1–5 | 3 | AB |
КЭГ Д |
| 1–4 | 4 | AB |
КЭГД Х |
| 1–3 | 1 | ЦЭГДГ А | |
| 1–2 | 2 | ЦЕГДХА Ф | |
| ЦЕГДАФ Б |
Современный метод [ править ]
В версии алгоритма Дюрстенфельда вместо того, чтобы вычеркивать выбранные буквы и копировать их в другом месте, они заменяются местами с последней еще не выбранной буквой. Начиная с букв от А до Н, как и раньше:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| ABCDEFGH |
Выберите случайное число j от 1 до 8, а затем поменяйте местами j- ю и 8-ю буквы. Итак, если случайное число равно, например, 6, поменяйте местами 6-ю и 8-ю буквы в списке:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| 1–8 | 6 | ABCDE H G | Ф |
Следующее случайное число выбирается от 1 до 7, а выбранная буква меняется местами с 7-й буквой. Например, если это 2, поменяйте местами 2-ю и 7-ю буквы:
| Диапазон | Рулон | Царапать | Результат |
|---|---|---|---|
| 1–7 | 2 | А.Г.CDEH | Б Ф |
Процесс повторяется до завершения перестановки:
| Диапазон | Рулон | Царапать | Результат | ||||
|---|---|---|---|---|---|---|---|
| 1–6 | 6 | АГКДЕ | Ч БФ | ||||
| 1–5 | 1 | Э НОД | ХБФ | ||||
| 1–4 | 3 | ЭГ Д | С АХБФ | ||||
| 1–3 | 3 | НАПРИМЕР | Д CAHBF | ||||
| 1–2 | 1 | Г | Э ДКАХБФ | ||||
После восьми шагов алгоритм завершен, и полученная перестановка — GEDCAHB F.
Варианты [ править ]
Алгоритм «наизнанку» [ править ]
 | Возможно, этот раздел содержит оригинальные исследования . ( Апрель 2017 г. ) |
Перетасовка Фишера-Йейтса, реализованная Дюрстенфельдом, представляет собой перетасовку на месте . То есть, учитывая предварительно инициализированный массив, он перемешивает элементы массива на месте, а не создает перетасованную копию массива. Это может быть преимуществом, если перемешиваемый массив большой.
Чтобы одновременно инициализировать и перетасовать массив, немного большей эффективности можно достичь, выполнив версию перетасовки «наизнанку». В этой версии элемент с номером 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 , количество элементов в источнике , не нужно знать заранее; нам нужно только иметь возможность определять конец исходных данных при его достижении. Ниже массив a строится итеративно, начиная с пустого, а .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
Алгоритм Саттоло [ править ]
| Циклический обмен ция |
Пример |
|---|---|
| BCDA | ABCD→DABC→CDAB→ BCDA →ABCD... |
| ДАБК | ABCD→BCDA→CDAB→ DABC →ABCD... |
| БДАК | ABCD→CADB→DCBA→ BDAC →ABCD... |
| АБР | ABCD→BDAC→DCBA→ CADB →ABCD... |
| CDBA | ABCD→DCAB→BADC→ CDBA →ABCD... |
| ДКАБ | ABCD→CDBA→BADC→ DCAB →ABCD... |
| Шесть (3!) циклических перестановок ABCD. сгенерировано алгоритмом Саттоло | |
Очень похожий алгоритм был опубликован в 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 :
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]
Сравнение с другими алгоритмами перетасовки [ править ]
Асимптотическая временная и пространственная сложность перетасовки Фишера-Йейтса оптимальна. В сочетании с высококачественным источником несмещенных случайных чисел он также гарантированно дает несмещенные результаты. По сравнению с некоторыми другими решениями оно также имеет то преимущество, что, если требуется только часть полученной перестановки, ее можно остановить на полпути или даже остановить и перезапустить несколько раз, генерируя перестановку постепенно по мере необходимости.
Наивный метод [ править ]
Наивный метод замены каждого элемента другим элементом, выбранным случайным образом из всех элементов, является предвзятым. [10] Различные перестановки будут иметь разную вероятность возникновения для каждого , поскольку количество различных перестановок, , не делит поровну количество случайных результатов алгоритма, . В частности, по постулату Бертрана будет хотя бы одно простое число . между ними и , и это число будет делиться но не разделить .
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 ), числа эффективно сортируются с использованием сортировки по основанию за время O ( n ). Подобно перетасовке Фишера-Йейтса, метод сортировки дает несмещенные результаты. Однако необходимо позаботиться о том, чтобы назначенные случайные числа никогда не дублировались, поскольку алгоритмы сортировки обычно не упорядочивают элементы случайным образом в случае равенства. [11] Кроме того, этот метод требует асимптотически большего пространства: O ( n ) дополнительного места для хранения случайных чисел по сравнению с O (1) пространства для перетасовки Фишера-Йейтса. Наконец, метод сортировки имеет простую параллельную реализацию, в отличие от перетасовки Фишера-Йейтса, которая является последовательной.
Вариант описанного выше метода, который нашел некоторое применение в языках, поддерживающих сортировку с помощью определяемых пользователем функций сравнения, заключается в перетасовке списка путем его сортировки с помощью функции сравнения, возвращающей случайные значения. Однако это, скорее всего, приведет к крайне неравномерному распределению, которое, кроме того, сильно зависит от используемого алгоритма сортировки. [12] [13] Например, предположим, что быстрая сортировка в качестве алгоритма сортировки используется с фиксированным элементом, выбранным в качестве первого элемента поворота . Алгоритм начинает сравнивать опорный элемент со всеми другими элементами, чтобы разделить их на меньшие и большие, а относительные размеры этих групп будут определять окончательное место опорного элемента. Для равномерно распределенной случайной перестановки каждая возможная конечная позиция должна быть одинаково вероятной для опорного элемента, но если каждое из начальных сравнений возвращает «меньше» или «больше» с равной вероятностью, тогда эта позиция будет иметь биномиальное распределение для p = 1/2, что дает позиции ближе к середине последовательности с гораздо более высокой вероятностью, чем позиции ближе к концам. Функции рандомизированного сравнения, применяемые к другим методам сортировки, таким как сортировка слиянием, могут давать результаты, которые кажутся более однородными, но это не совсем так, поскольку объединение двух последовательностей путем многократного выбора одной из них с равной вероятностью (пока выбор не будет вызван исчерпанием одной последовательность) не дает результатов с равномерным распределением; вместо этого вероятность выбора последовательности должна быть пропорциональна количеству оставшихся в ней элементов. [ нужна ссылка ] . Фактически ни один метод, который использует только двусторонние случайные события с равной вероятностью ( «подбрасывание монеты» ), повторяемые ограниченное число раз, не может производить перестановки последовательности (более двух элементов) с равномерным распределением, поскольку каждое выполнение вероятностью пути будет рациональное число со знаменателем, степенью 2 , а требуемая вероятность 1/ n ! для каждой возможной перестановки не тот вид [ нужна ссылка ] .
В принципе, этот метод перетасовки может даже привести к сбоям программы, таким как бесконечные циклы или нарушения доступа, поскольку правильность алгоритма сортировки может зависеть от свойств отношения порядка (например, транзитивности ), которых определенно не будет при сравнении, производящем случайные значения. [14] Хотя такое поведение не должно происходить с процедурами сортировки, которые никогда не выполняют сравнение, результат которого можно с уверенностью предсказать (на основе предыдущих сравнений), могут быть веские причины для преднамеренного проведения таких сравнений. Например, тот факт, что любой элемент должен сравниваться равным самому себе, позволяет использовать его в качестве контрольного значения по соображениям эффективности, и в этом случае функция случайного сравнения нарушит алгоритм сортировки.
предвзятости Потенциальные источники
Необходимо соблюдать осторожность при реализации перетасовки Фишера-Йейтса, как при реализации самого алгоритма, так и при генерации случайных чисел, на которых он построен, в противном случае результаты могут показать заметное смещение. Ниже перечислен ряд распространенных источников предвзятости.
Ошибки реализации [ править ]
Распространенной ошибкой при реализации перетасовки Фишера-Йейтса является выбор случайных чисел из неправильного диапазона. Может показаться, что ошибочный алгоритм работает правильно, но он не будет выдавать все возможные перестановки с равной вероятностью, а может вообще не выдавать определенные перестановки. Например, распространенной ошибкой отклонения на единицу будет выбор индекса j записи для замены в приведенном выше примере , который всегда будет строго меньше индекса i записи, с которой она будет заменена. Это превращает перетасовку Фишера-Йейтса в алгоритм Саттоло , который производит только перестановки, состоящие из одного цикла, включающего все элементы: в частности, с этой модификацией ни один элемент массива никогда не может оказаться в исходном положении.
Аналогично, всегда выбор j из всего диапазона допустимых индексов массива на каждой итерации также дает результат, который является предвзятым, хотя и менее очевидным. Это видно из того, что при этом получается n н различных возможных последовательностей перестановок, тогда как существует только n ! возможные перестановки массива из n элементов. Поскольку н н никогда не может делиться на n без остатка ! когда n > 2 (поскольку последнее делится на n −1, которое не имеет общих простых делителей с 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 (как в случае с исходными таблицами Фишера и Йейтса), что составляет 100 значений, и что вы хотите получить несмещенное случайное число от 0 до 15 (16 ценности). Если вы просто разделите числа на 16 и возьмете остаток, вы обнаружите, что числа 0–3 встречаются примерно на 17% чаще, чем другие. Это связано с тем, что 16 не делит 100 поровну: наибольшее кратное 16, меньшее или равное 100, составляет 6 × 16 = 96, и именно числа в неполном диапазоне 96–99 вызывают смещение. Самый простой способ решить проблему — отбросить эти числа, прежде чем брать остаток, и продолжать попытки снова, пока не появится число в подходящем диапазоне. Хотя в принципе это может, в худшем случае, занять вечность, ожидаемое количество повторных попыток всегда будет меньше одной.
Схожая проблема возникает с реализациями, которые сначала генерируют случайное число с плавающей запятой — обычно в диапазоне [0,1] — а затем умножают его на размер желаемого диапазона и округляют в меньшую сторону. Проблема здесь в том, что случайные числа с плавающей запятой, как бы тщательно они ни генерировались, всегда имеют лишь конечную точность. Это означает, что в любом заданном диапазоне существует только конечное число возможных значений с плавающей запятой, и если диапазон разделить на несколько сегментов, которые не делят это число поровну, в некоторых сегментах будет больше возможных значений, чем в других. Хотя результирующее смещение не будет демонстрировать такую же систематическую тенденцию к снижению, как в предыдущем случае, оно все равно будет присутствовать.
Псевдослучайные генераторы [ править ]
|
| семенные кусочки | максимальная длина списка |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 3 | 3 |
| 5 | 4 |
| 7 | 5 |
| 10 | 6 |
| 13 | 7 |
| 16 | 8 |
| 22 | 10 |
| 24 | 10 |
| 32 | 12 |
| 48 | 16 |
| 64 | 20 |
| 128 | 34 |
| 160 | 40 |
| 226 | 52 |
| 256 | 57 |
| 512 | 98 |
| 1024 | 170 |
| 1600 | 245 |
| 19937 | 2080 |
| 44497 | 4199 |
Дополнительная проблема возникает, когда тасование Фишера-Йейтса используется с генератором псевдослучайных чисел или ГПСЧ: поскольку последовательность чисел, выводимых таким генератором, полностью определяется его внутренним состоянием в начале последовательности, тасование, вызванное таким Генератор не может создать больше различных перестановок, чем количество различных возможных состояний генератора. [16] Даже когда количество возможных состояний превышает количество перестановок, нерегулярный характер отображения последовательностей чисел в перестановки означает, что некоторые перестановки будут происходить чаще, чем другие. Таким образом, чтобы минимизировать погрешность, количество состояний ГПСЧ должно превышать количество перестановок как минимум на несколько порядков.
Например, встроенный генератор псевдослучайных чисел, предоставляемый многими языками программирования и/или библиотеками, часто может иметь только 32 бита внутреннего состояния, что означает, что он может выдавать только 2 бита. 32 разные последовательности чисел. Если такой генератор использовать для перетасовки колоды из 52 игральных карт , он сможет произвести лишь очень небольшую часть из 52! ≈ 2 225.6 возможные перестановки. Генератор с внутренним состоянием менее 226 бит не может создать все возможные перестановки колоды из 52 карт.
Ни один генератор псевдослучайных чисел не может создавать более различные последовательности, начиная с точки инициализации, чем существуют различные начальные значения, которыми он может быть инициализирован. Таким образом, генератор, имеющий 1024 бита внутреннего состояния, но инициализируемый 32-битным начальным числом, все равно может выдать только 2 бита. 32 различные перестановки сразу после инициализации. Он может производить больше перестановок, если использовать генератор очень много раз, прежде чем начать использовать его для генерации перестановок, но это очень неэффективный способ увеличения случайности: предположим, что можно организовать использование генератора случайных чисел до миллиарда. , скажем 2 30 для простоты время между инициализацией и генерацией перестановок, тогда число возможных перестановок по-прежнему составляет всего 2 62 .
Еще одна проблема возникает, когда простой линейный конгруэнтный ГПСЧ используется с описанным выше методом сокращения диапазона «раздели и возьми остаток». Проблема здесь в том, что младшие биты линейного конгруэнтного ГПСЧ с модулем 2 и менее случайны, чем старшие: [6] сами младшие n бит генератора имеют период не более 2 н . Когда делитель представляет собой степень двойки, взятие остатка по сути означает отбрасывание старших битов, в результате чего получается значительно меньшее случайное значение. Если LCG имеет простое число по модулю, применяются другие правила, но такие генераторы встречаются редко. Это пример общего правила, согласно которому некачественный ГСЧ или ГПСЧ приводит к некачественным перетасовкам.
См. также [ править ]
- RC4 — поточный шифр, основанный на перетасовке массива.
- Отбор проб пласта , в частности алгоритм R, который является разновидностью перетасовки Фишера-Йейтса.
Ссылки [ править ]
- ^ Эберл, Мануэль (2016). «Перетасовка Фишера-Йейтса» . Архив формальных доказательств . Проверено 28 сентября 2023 г.
- ^ Смит, Джеймс (2 апреля 2023 г.). «Давайте сделаем перетасовку Кнута» . Структура проекта Голанг . Проверено 03 апреля 2023 г.
- ^ Фишер, Рональд А .; Йейтс, Фрэнк (1948) [1938]. Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований (3-е изд.). Лондон: Оливер и Бойд. стр. 26–27. OCLC 14222135 . Примечание: издание 6-е, ISBN 0-02-844720-4 доступен в Интернете , но дает другой алгоритм перетасовки Ч.Р. Рао .
- ^ Дурстенфельд, Р. (июль 1964 г.). «Алгоритм 235: Случайная перестановка» (PDF) . Коммуникации АКМ . 7 (7): 420. дои : 10.1145/364520.364540 . S2CID 494994 .
- ^ Кнут, Дональд Э. (1969). Получисловые алгоритмы . Искусство компьютерного программирования. Том. 2. Ридинг, Массачусетс: Аддисон-Уэсли. стр. 139–140. OCLC 85975465 .
- ↑ Перейти обратно: Перейти обратно: а б Кнут (1998). Получисловые алгоритмы . Искусство компьютерного программирования. Том. 2 (3-е изд.). Бостон: Аддисон-Уэсли. стр. 12–15, 145–146. ISBN 0-201-89684-2 . ОСЛК 38207978 .
- ^ Блэк, Пол Э. (19 декабря 2005 г.). «Перетасовка Фишера-Йейтса» . Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Проверено 9 августа 2007 г.
- ^ Саттоло, Сандра (30 мая 1986 г.). «Алгоритм генерации случайной циклической перестановки». Письма об обработке информации . 22 (6): 315–3017. дои : 10.1016/0020-0190(86)90073-6 .
- ^ Уилсон, Марк К. (21 июня 2004 г.). «Обзор алгоритма Саттоло» (PDF) . В Ф. Чизаке (ред.). Отчет об исследовании INRIA . Семинар по алгоритмам 2002–2004 гг . Том. 5542. Краткое содержание Эрика Фьюзи. стр. 105–108. ISSN 0249-6399 .
- ^ «Опасность наивности» . Джефф Этвуд . 07.12.2007 . Проверено 7 декабря 2019 г.
- ^ «Доказуемо совершенные алгоритмы перемешивания» . Олег Киселёв . 3 сентября 2001 г. Проверено 9 июля 2013 г.
- ^ «Простая перетасовка, которая, в конце концов, оказалась не такой уж и простой» . требуют «мозгов» . 19 июня 2007 г. Проверено 9 августа 2007 г.
- ^ «Выполнение Microsoft Shuffle: сбой алгоритма при голосовании в браузере» . Роб Вейр: Античный нрав . 27 февраля 2010 г. Проверено 28 февраля 2010 г.
- ^ «Написание функции сравнения сортировки, redux» . требуют «мозгов» . 08 мая 2009 г. Проверено 8 мая 2009 г.
- ^ Библиотека GNU C: Случайный ISO
- ^ Арндт, Йорг (2009). Генерация случайных перестановок (кандидатская диссертация) (PDF) . Австралийский национальный университет. п. 9 . Проверено 25 апреля 2018 г.