106
правок
Изменения
м
*''swap(i, j);'' меняет местами числа на местах i и j в массиве <tex> a </tex><br/>
'''function''' randomPermutation(a:array[1..n] of integer):array[1..n] of integer // n — длина массива ''' for''' i = 1 '''to''' n j = '''<tex>\mathrm{random'''(1..i)}</tex> ''' <tex>\mathrm{swap'''(a[i], [j])}</tex> '''return'''(a)Этот алгоритм носит имя Фишера-Йетса.
Следует проявлять осторожность при реализации алгоритма Фишера-Йетса, как в части самого алгоритма, так и для генератора случайных чисел for i = 1..n swap(random(1..n), на котором он базируетсяrandom(1.Некоторые общие ошибки реализации приведены ниже.n))
=== Ошибки при реализации алгоритма ===Общей ошибкой при реализации тасования Фишера – Йетса является выбор случайных чисел из неверного интервала.Дефектный алгоритм может казаться работающим корректно, но он не создает все возможные перестановки с равной вероятностью, а некоторые перестановки может вообще не создать.Например, общая ошибка занижения или завышения на единицу может возникнуть при выборе индекса ''j'' переставляемого элемента в [[#Современный алгоритм|примере выше]] всегда меньше индекса ''i'', с которым элемент должен быть переставлен.В результате вместо тасования Фишера-Йета получим алгоритм Саттоло, который образует перестановки, затрагивающие все элементы. В частности, самом деле: число способов сгенерировать последовательность в этом первом случае никакой элемент не может оказаться на начальной позиции. [[Файл:Probabilities7.png|200px|thumb|right|Вероятность того, что элемент i окажется на позиции j при неверной реализации алгоритма]] Подобным образом, выбор ''j'' из всех индексов в массиве на каждой итерации также образует неравновероятные перестановки, хотя и не столь очевидно.Это можно установить из того факта, что такая реализация образует ''n''равно <suptex>''n''^n</suptex> различных обменов местами для элементов, в то время как существует всего [[Факториал|''n''!]] возможных перестановок массива из ''n'' элементов.Поскольку ''n''<sup>''n''во втором равно </suptex> никогда не может делиться на ''n''! без остатка при ''n'' > 2 (поскольку ''n''! делится на число ''n''−1, которое не имеет с ''n'' общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.Рассмотрим конкретный пример перестановок трех элементов [1, ^2, 3]. Имеется 6 возможных перестановок этого набора (3! = 6), но алгоритм образует 27 перетасовок (3<sup>3^n</suptex> = 27). В этом случае [1, 2, 3], [3, 1, 2], и [3, 2, 1] встречаются по 4 раза в 27 перетасовках, в то время как оставшиеся 3 встречаются по 5 раз. Матрица справа показывает вероятность появления каждого элемента из списка длины 7 в конечной позиции. Заметьте, что для большинства элементов остаться при тасовании на своей начальной позиции (главная диагональ матрицы) имеет минимальную вероятность, а сдвинуться на одну позицию влево - максимальную. === Нарушение равномерности распределения при взятии по модулю === Алгоритм Фишера-Йетса использует выборку равномерно распределенных случайных чисел из различных диапазонов. Большинство генераторов случайных чисел, однако, как настоящих случайных, так и псевдослучайных дают числа в фиксированном диапазоне, скажем от 0 до 2всего последовательностей <suptex>32n!</suptex>−1. Простой и обычно используемый метод приведения таких чисел к нужному интервалу заключается в использовании сравнения по модулюДля того, то естьчтобы сгенерированные последовательности были равновероятны, взятия остатка от деления на верхнюю границу. Необходимость генерировать случайные числа во всех интервалах от 0–1 до 0–''n'' гарантируетнеобходимо хотя бы, что некоторые из этих границ не будут делить естественную границу генератора нацело.Как результат, распределение не будет равномерным и маленькие остатки будут встречаться чаще. Предположим, например, что генератор дает случайные числа между 0 и 99 (как чтобы число способов получить последовательность было у Фишера и Йетса в кратно их оригинальных таблицах), а вы хотите получить случайные числа между 0 и 15. Если вы просто находите остаток числа при делении на 16, вы обнаружите, что числа 0–3 встречаются на 17% чаще, чем остальныеобщему числу. Причина этого заключается в том, что 16 не делит 100 нацело – наибольшее число, кратное 16 и не превышающее 100 То есть 6×16 = 96, а оставшиеся числа из диапазона 96–99 создают неравномерность. Самый простой способ избежать этой проблемы заключается в отбрасывании таких чисел до взятия остатка. Хотя, в принципе, числа из такого интервала могут попадаться, математическое ожидание числа повторных попыток всегда меньше единицы. Похожая проблема возникает в первом случае использования генератора случайных чисел, дающего числа с плавающей запятой, обычно в диапазоне [0,1). Полученное число умножают на размер желаемого диапазона и округляют. Проблема здесь в том, что даже аккуратно сгенерированные случайные числа с плавающей запятой имеют конечную точность, что означает, что можно получить только конечное число возможных чисел с плавающей запятой, и, как и в случае выше, эти числа разбиваются на сегменты, которые не делят число нацело и некоторые сегменты получают большую вероятность появления, чем другие.=== Псевдослучайные генераторы: проблему, обусловленные внутренними состояниями генератора случайных чисел, начальными параметрами и использованием === Дополнительные проблемы появляются при использовании генератора псевдослучайных чисел необходимо <tex>(ГПСЧn^n).Генерация псевдослучайной последовательности таких генераторов полностью определяется их внутренним состоянием в начале генерации.Программа тасования, опирающаяся на такой генератор, не может создать больше перестановок, чем число внутренних состояний генератора. Даже когда число возможных состояний генератора перекрывает число перестановок, некоторые перестановки могут появляться чаще, чем другие. Во избежание появления неравномерности распределения число внутренних состояний генератора случайных чисел должно превосходить число перестановок на несколько порядков. Например, встроенный генератор псевдослучайных чисел, имеющийся во многих языках программирования и библиотеках использует, обычно, 32-битное число для внутренних состояний, что означает, что такой генератор может создать только 2<sup>32</sup> различных случайных чисел. Если такой генератор будет использоваться для тасования колоды из 52 игральных карт, он может может создать очень маленькую часть от [[Факториал|52\vdots n!]] ≈ 2<sup>225.6</suptex> возможных перестановок. Генератор с менее чем 226-битным числом внутренних состояний не может создать все перестановки колоды из 52 игральных карт. Считается, что для создания равномерного распределения необходим генератор, имеющий не менее 250-битного числа состояний. Естественно, что никакой генератор псевдослучайных чисел не может создать больше случайных последовательностей, задающихся различными начальными данными, чем число этих начальных данных. Так, генератор с 1024-битным числом внутренних состояний, для которого задаются 32-битные начальные параметры, может создать лишь 2а во втором случае <suptex>32</sup> различных последовательностей перестановок. Можно получить больше перестановок, выбирая достаточно много случайных чисел из генератора до начала его использования в алгоритме тасования, но такой подход очень неэффективен – выборка, скажем, ((n^2<sup>30</sup> случайных чисел до использования последовательности в алгоритме тасования повышает число перестановок только до 2<sup>62</sup>. Ещё одна проблема появляется при использовании простого линейного конгруэнтного ГПСЧ, когда для уменьшения интервала случайных чисел используется остаток от деления, как было указано выше. Проблема здесь в том, что младшие биты линейного конгруэнтного ГПСЧ менее случайны по сравнению со старшими битами – младшие '')^n'' бит имеют период максимум 2<sup>'') \vdots n''!</suptex>. Если делитель является степенью двойки, взятие остатка означает отбрасывание старших битов, что приводит к существенному уменьшению случайности. Наконец, следует заметить, что даже использование прекрасного генератора, изъян в алгоритме может возникнуть из-за неправильного использования генератора. Представим себезаведомо не выполняется при подстановке любого нечетного числа, например, что реализация алгоритма на языке Java создает новый генератор для каждого вызова процесса тасования без задания параметров в конструкторе. Для инициализации генератора будет использовано текущее время (System.currentTimeMillis()). Таким образом, два вызова начиная с разницей во времени менее миллисекунды дадут идентичные перестановки. Это случится почти наверняка, если тасование происходит многократно и быстро, что приведет к крайне неравномерному распределению перестановок. Такая же проблема может возникнуть при получении случайных чисел из двух различных потоков. Правильнее использовать один статический экземпляр генератора, определенный вне процедуры тасования3.
==Ссылки==
Нет описания правки
'''Тасование Фишера–Йетса''' (названо в честь Рональда Фишера(Ronald Fisher) и Франка Йетса (Frank Yates)) – алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.
Основная процедура тасования Фишера–Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
Пусть <br/>
*''random(1..i);'' генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
Следующий алгоритм решает задачу:
==Обоснование==
Проведем доказательство по индукции. Всего перестановок <tex> n! </tex>, поэтому вероятность каждой из них должна быть равна <tex> \frac {1}{n!}</tex>. Показажем, что на каждом i-ом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.
шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
== Потенциальные источники неравномерности распределения Неправильные способы реализации==Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно: for i = 1..n swap(i, random(1..n))
==Примечание==
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Йетс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>
==ЛитератураИсточники==
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера–Йетса]
==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4%D1%8B_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B3%D0%BE_%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетания]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
