Метод генерации случайной перестановки, алгоритм Фишера-Йетса

Тасование Фишера–Йетса (названо в честь Рональда Фишера(Ronald Fisher) и Франка Йетса (Frank Yates)) – алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера–Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.

Постановка задачи

Необходимо сгенерировать случайную перестановку из [math] n [/math] чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.

Решение

Пусть

• random(1..i); генерирует случайное число в интервале [math] [1;\; i] [/math]
  
• swap(i, j); меняет местами числа на местах i и j в массиве [math] a [/math]
  

Следующий алгоритм решает задачу:

 function randomPermutation(a:array[1..n] of integer):array[1..n] of integer // n — длина массива
  for i = 1 to n
    j = random(1..i)
    swap(i, j)
 return(a)

Этот алгоритм носит имя Фишера-Йетса.

Обоснование

Проведем доказательство по индукции. Всего перестановок [math] n! [/math], поэтому вероятность каждой из них должна быть равна [math] \frac {1}{n!}[/math]. Показажем, что на каждом i-ом шаге цикла любая перестановка из первых [math]i[/math] элементов равновероятна.

• при [math] i = 1 [/math] перестановка всего одна, и, очевидно, что база верна
• пусть при [math] i = k - 1 [/math] каждая перестановка первых [math]i[/math] элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки на [math]i[/math]-ом шаге цикла равна [math] \frac {1}{(k-1)!}[/math]

при [math] i = k [/math]:

[math] a = \langle a_{1}, a_{2}, ..., a_{k-1}, k, ... \rangle [/math]

после [math]swap(i, random(1..i))[/math] вероятность какого-то числа оказаться на [math]k[/math]-ом месте равна [math]\frac{1}{k}[/math]. Вероятность же какой-то перестановки первых [math](k-1)[/math] элементов при известном [math]a_{k}[/math] останется [math] \frac {1}{(k-1)!}[/math], что в результате дает, что вероятность перестановки первых [math]k[/math] элементов равна [math] \frac {1}{k!}[/math]

Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за [math] n [/math] шагов, таким образом автоматически получается, что все [math] n![/math] перестановок равновероятны.

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

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

Ошибки при реализации алгоритма

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

Вероятность того, что элемент i окажется на позиции j при неверной реализации алгоритма

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

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

Нарушение равномерности распределения при взятии по модулю

Алгоритм Фишера-Йетса использует выборку равномерно распределенных случайных чисел из различных диапазонов. Большинство генераторов случайных чисел, однако, как настоящих случайных, так и псевдослучайных дают числа в фиксированном диапазоне, скажем от 0 до 2³²−1. Простой и обычно используемый метод приведения таких чисел к нужному интервалу заключается в использовании сравнения по модулю, то есть, взятия остатка от деления на верхнюю границу. Необходимость генерировать случайные числа во всех интервалах от 0–1 до 0–n гарантирует, что некоторые из этих границ не будут делить естественную границу генератора нацело. Как результат, распределение не будет равномерным и маленькие остатки будут встречаться чаще.

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

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

Псевдослучайные генераторы: проблему, обусловленные внутренними состояниями генератора случайных чисел, начальными параметрами и использованием

Дополнительные проблемы появляются при использовании генератора псевдослучайных чисел (ГПСЧ). Генерация псевдослучайной последовательности таких генераторов полностью определяется их внутренним состоянием в начале генерации. Программа тасования, опирающаяся на такой генератор, не может создать больше перестановок, чем число внутренних состояний генератора. Даже когда число возможных состояний генератора перекрывает число перестановок, некоторые перестановки могут появляться чаще, чем другие. Во избежание появления неравномерности распределения число внутренних состояний генератора случайных чисел должно превосходить число перестановок на несколько порядков.

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

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

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

Наконец, следует заметить, что даже использование прекрасного генератора, изъян в алгоритме может возникнуть из-за неправильного использования генератора. Представим себе, например, что реализация алгоритма на языке Java создает новый генератор для каждого вызова процесса тасования без задания параметров в конструкторе. Для инициализации генератора будет использовано текущее время (System.currentTimeMillis()). Таким образом, два вызова с разницей во времени менее миллисекунды дадут идентичные перестановки. Это случится почти наверняка, если тасование происходит многократно и быстро, что приведет к крайне неравномерному распределению перестановок. Такая же проблема может возникнуть при получении случайных чисел из двух различных потоков. Правильнее использовать один статический экземпляр генератора, определенный вне процедуры тасования.

Примечание

• Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Йетс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).
  
• Нетрудно увидеть, что сложность алгоритма [math] O(n)[/math]

Литература

• Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2

Ссылки

• Википедия - Тасование Фишера–Йетса
• Интерактивный пример