stringtranslate.com

Перетасовка Фишера–Йейтса

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

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

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

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

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

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

При условии, что случайные числа, выбранные на шаге 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 и так далее, всегда повторяя процесс вычеркивания, как указано выше:

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

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

Выберите случайное число j от 1 до 8, а затем поменяйте местами j -ю и 8-ю буквы. Так, если случайное число равно, например, 6, поменяйте местами 6-ю и 8-ю буквы в списке:

Выбирается следующее случайное число от 1 до 7, и выбранная буква меняется местами с 7-й буквой. Если это, например, 2, то меняем местами 2-ю и 7-ю буквы:

Процесс повторяется до тех пор, пока перестановка не будет завершена:

После восьми шагов алгоритм будет завершен, а результирующая перестановка — GEDCAHB F.

Реализация Python

В этом примере показана простая реализация перемешивания Фишера-Йетса на языке Python.

импорт  случайный def  shuffle ( n :  int )  ->  list [ int ]: числа  =  список ( диапазон ( n )) перетасованно  =  [] в то время как  числа : к  =  случайный . randint ( 0 ,  len ( числа )  -  1 ) перетасовал . добавить ( числа [ k ]) числа . поп ( k ) вернуться  перетасованным

Варианты

Алгоритм «изнутри-наружу»

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

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

Чтобы инициализировать массив a из n элементов случайным образом перемешанной копией source , начиная с 0: for  i  от 0 до  n − 1 do  j ← случайное целое число, такое что 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 строится итеративно, начиная с пустого, а a .length представляет текущее количество видимых элементов.

Чтобы инициализировать пустой массив a случайно перемешанной копией источника , длина которой неизвестна: while  source .moreDataAvailable j ← случайное целое число, такое что 0 ≤ j ≤ a .length if j = a .length a .append( source .next) else  a .append( a [ j ]) a [ j ] ← source .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 items [ j ], items [ i ] = items [ i ], items [ j ]

Параллельные варианты

Разработано несколько параллельных алгоритмов тасования, основанных на методе Фишера—Йетса.

В 1990 году Андерсон разработал параллельную версию для машин с небольшим числом процессоров, имеющих доступ к общей памяти. [10] Алгоритм генерирует случайные перестановки равномерно, пока оборудование работает честно.

В 2015 году Бахер и др. создали MERGESHUFFLE — алгоритм, который делит массив на блоки примерно одинакового размера, использует алгоритм Фишера-Йетса для перемешивания каждого блока, а затем рекурсивно использует случайное слияние для получения перемешанного массива. [11]

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

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

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

Наивный метод замены каждого элемента другим элементом, выбранным случайным образом из всех элементов, является предвзятым. [12] Различные перестановки будут иметь разные вероятности генерации для каждого , поскольку число различных перестановок , не делит поровну число случайных результатов алгоритма . В частности, по постулату Бертрана будет по крайней мере одно простое число между и , и это число будет делить , но не делить .

из  случайного  импорта  randrangedef  naive_shuffle ( items )  ->  None : """Наивный метод. Это пример того, как не следует делать — используйте вместо этого метод Фишера-Йетса.""" 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 ). Как и метод перемешивания Фишера–Йетса, метод сортировки дает несмещенные результаты. Однако необходимо позаботиться о том, чтобы назначенные случайные числа никогда не дублировались, поскольку алгоритмы сортировки обычно не упорядочивают элементы случайным образом в случае ничьей. [13] Кроме того, этот метод требует асимптотически большего пространства: O ( n ) дополнительного пространства для хранения случайных чисел по сравнению с O (1) пространства для перемешивания Фишера–Йетса. Наконец, метод сортировки имеет простую параллельную реализацию, в отличие от перемешивания Фишера–Йетса, которое является последовательным.

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

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

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

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

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

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

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

Аналогично, всегда выбирая 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. [17] Простой и часто используемый способ принудительного помещения таких чисел в желаемый диапазон — это применение оператора modulo ; [18] то есть деление их на размер диапазона и взятие остатка. Однако необходимость в перетасовке Фишера-Йетса генерировать случайные числа в каждом диапазоне от 0–1 до 0– n почти гарантирует, что некоторые из этих диапазонов не будут равномерно делить естественный диапазон генератора случайных чисел. Таким образом, остатки не всегда будут равномерно распределены, и, что еще хуже, смещение будет систематически в пользу малых остатков. [19] [19] : Классический Modulo (смещенный) 

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

Метод получения случайных чисел в требуемых диапазонах, который является несмещенным и почти никогда не выполняет дорогостоящую операцию по модулю, был описан в 2018 году Даниэлем Лемиром. [21]

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

Дополнительные затраты на устранение «смещения по модулю» при генерации случайных целых чисел для тасовки Фишера-Йетса зависят от подхода (классический модуль, умножение с плавающей точкой или целочисленное умножение Лемира), размера массива, который необходимо тасовать, и используемого генератора случайных чисел. [19] : Сравнительный анализ ... 

Генераторы псевдослучайных чисел

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

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

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

Еще одна проблема возникает, когда простой линейный конгруэнтный PRNG используется с методом деления и взятия остатка для сокращения диапазона, описанным выше. Проблема здесь в том, что младшие биты линейного конгруэнтного PRNG с модулем 2 e менее случайны, чем старшие: [6] младшие n биты генератора сами по себе имеют период не более 2 n . Когда делитель является степенью двойки, взятие остатка по сути означает отбрасывание старших бит, так что в итоге получается значительно менее случайное значение. Другие правила применяются, если LCG имеет простой модуль, но такие генераторы встречаются редко. Это пример общего правила, согласно которому некачественный RNG или PRNG будет производить некачественные перетасовки.

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

Ссылки

  1. ^ Эберл, Мануэль (2016). «Fisher–Yates shuffle». Архив формальных доказательств . Получено 28 сентября 2023 г. .
  2. ^ Смит, Джеймс (2023-04-02). «Давайте сделаем перетасовку Кнута». Структура проекта Golang . Получено 2023-04-03 .
  3. ^ Фишер, Рональд А .; Йейтс, Фрэнк (1948) [1938]. Статистические таблицы для биологических, сельскохозяйственных и медицинских исследований (3-е изд.). Лондон: Oliver & Boyd. С. 26–27. OCLC  14222135. Примечание: 6-е издание, ISBN 0-02-844720-4 , доступно в Интернете, но в нем представлен другой алгоритм перемешивания, разработанный CR Rao . 
  4. ^ Дюрстенфельд, Р. (июль 1964 г.). "Алгоритм 235: Случайная перестановка" (PDF) . Сообщения ACM . 7 (7): 420. doi :10.1145/364520.364540. S2CID  494994.
  5. ^ Кнут, Дональд Э. (1969). Получисленные алгоритмы . Искусство программирования. Т. 2. Рединг, Массачусетс: Addison–Wesley. С. 139–140. OCLC  85975465.
  6. ^ ab Knuth (1998). Получисленные алгоритмы . Искусство программирования. Т. 2 (3-е изд.). Бостон: Addison–Wesley. С. 12–15, 145–146. ISBN 0-201-89684-2. OCLC  38207978.
  7. ^ Блэк, Пол Э. (2005-12-19). "Fisher–Yates shuffle". Словарь алгоритмов и структур данных . Национальный институт стандартов и технологий . Получено 2007-08-09 .
  8. ^ Саттоло, Сандра (1986-05-30). «Алгоритм для генерации случайной циклической перестановки». Information Processing Letters . 22 (6): 315–3017. doi :10.1016/0020-0190(86)90073-6.
  9. ^ Уилсон, Марк К. (2004-06-21). "Обзор алгоритма Саттоло" (PDF) . В F. Chyzak (ред.). Отчет об исследовании INRIA . Семинар по алгоритмам 2002–2004. Том 5542. Резюме Эрика Фьюзи. С. 105–108. ISSN  0249-6399.
  10. ^ Ричард, Андерсон (1990). "Параллельные алгоритмы для генерации случайных перестановок на машине с общей памятью". Труды второго ежегодного симпозиума ACM по параллельным алгоритмам и архитектурам - SPAA '90 . стр. 95–102. doi :10.1145/97444.97674. ISBN 0-89791-370-1. Получено 20 сентября 2024 г. .
  11. ^ Бахер, Аксель; Бодини, Оливье; Холлендер, Александрос; Лумброзо, Жереми (2015). «MERGESHUFFLE: очень быстрый параллельный алгоритм случайной перестановки». arXiv : 1508.03167 [cs.DS].
  12. ^ "Опасность наивности". Джефф Этвуд . 2007-12-07 . Получено 2019-12-07 .
  13. ^ "Доказуемо совершенные алгоритмы перемешивания". Олег Киселёв . 3 сентября 2001 г. Получено 09.07.2013 .
  14. ^ "Простая перетасовка, которая в конце концов оказалась не такой уж простой". требуется 'brain' . 2007-06-19 . Получено 2007-08-09 .
  15. ^ "Выполнение Microsoft Shuffle: Ошибка алгоритма в голосовании браузера". Роб Вейр: An Antic Disposition . 2010-02-27 . Получено 2010-02-28 .
  16. ^ "Написание функции сравнения сортировок, redux". require 'brain' . 2009-05-08 . Получено 2009-05-08 .
  17. ^ Библиотека GNU C: Случайный ISO
  18. ^ "Равномерность случайных чисел, взятых по модулю N". stackoverflow . Получено 13 сентября 2024 г. .
  19. ^ abcd O'Neill, ME (22 июля 2018 г.). "Эффективное создание числа в диапазоне" . Получено 23 августа 2024 г.
  20. ^ Summit, Steve (1995). "Вопрос 13.16: Как получить случайные целые числа в определенном диапазоне?". Часто задаваемые вопросы по программированию на языке C: часто задаваемые вопросы. Addison-Wesley. ISBN 0-201-84519-9. Получено 8 сентября 2024 г. .
  21. ^ ab Lemire, Daniel (23 февраля 2019 г.). «Быстрая генерация случайных целых чисел в интервале». ACM Transactions on Modeling and Computer Simulation . 29 (1): 1–12. arXiv : 1805.10941 . doi : 10.1145/3230636. S2CID  44061046.
  22. ^ Арндт, Йорг (2009). Генерация случайных перестановок (диссертация) (PDF) . Австралийский национальный университет. стр. 9 . Получено 25 апреля 2018 г. .
  23. ^ Пфафф, Бен. «Как перетасовать содержимое массива?» . Получено 13 сентября 2024 г.
  24. ^ Occil, Peter. «Рекомендации по генератору случайных чисел для приложений — перетасовка». peteroupc.github.io . Получено 17 сентября 2024 г.

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