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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Обоснование)
(не показано 30 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Тасование Фишера–Йетса''' (названо в честь Рональда Фишера(Ronald Fisher) и Франка Йетса (Frank Yates)) алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.   
+
'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.   
Основная процедура тасования Фишера–Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
+
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>.
 +
==Применение алгоритма==
 +
{{Задача
 +
|definition = Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
 +
}}
 +
===Решение:===
  
==Постановка задачи==
 
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
 
==Решение==
 
 
Пусть <br/>
 
Пусть <br/>
*''random(1..i);'' генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
+
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в отрезке <tex> [1;\; i] </tex> <br/>
*''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 = '''random'''(1..i)
 
    '''swap'''(i, j)
 
  '''return'''(a)
 
Этот алгоритм носит имя Фишера-Йетса.
 
==Обоснование==
 
Проведем доказательство по индукции. Всего перестановок <tex> n! </tex>, поэтому вероятность каждой из них должна быть равна <tex> \frac {1}{n!}</tex>. Показажем, что на каждом i-ом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.
 
* при <tex> i = 1 </tex> перестановка всего одна, и, очевидно, что база верна
 
* пусть при <tex> i = k - 1 </tex> каждая перестановка первых <tex>i</tex> элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки  на <tex>i</tex>-ом шаге цикла равна <tex> \frac {1}{(k-1)!}</tex>
 
: при <tex> i = k </tex>:
 
: <tex> a:array[ a_{1}, a_{2}, ..., a_{k-1}, k, ... ] </tex>
 
: после <tex>swap(i, random(1..i))</tex> вероятность какого-то числа оказаться на <tex>k</tex>-ом месте равна <tex>\frac{1}{k}</tex>. Вероятность же какой-то перестановки первых <tex>(k-1)</tex> элементов при известном <tex>a_{k}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность перестановки первых <tex>k</tex> элементов равна <tex> \frac {1}{k!}</tex>
 
<br/>
 
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex>
 
шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
 
  
== Потенциальные источники неравномерности распределения ==
+
  '''int[n]''' randomPermutation(a: '''int[n]'''):  <font color = green> // '''n''' {{---}} длина перестановки </font>
 +
    '''for''' i = n '''downto''' 1
 +
      j = random(1..i)
 +
      swap(a[i], a[j])
 +
    '''return''' a
  
Следует проявлять осторожность при реализации алгоритма Фишера-Йетса, как в части самого алгоритма, так и для генератора случайных чисел, на котором он базируется.
+
==Обоснование==
Некоторые общие ошибки реализации приведены ниже.
+
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <tex> n</tex> способов выбрать <tex>1</tex> элемент, <tex> n - 1</tex> способов выбрать <tex>2</tex> элемент... <tex> 1</tex> способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины <tex> n</tex> мы можем получить  <tex> n \times (n - 1) \times \ldots \times 1 = n!  </tex> способами, что совпадает с числом различных перестановок длины <tex> n</tex>. Это означает, что вероятность выбрать любую перестановку длины <tex> n</tex> равна <tex> \dfrac{1}{n!}</tex>, то есть все перестановки равновероятны.
  
=== Ошибки при реализации алгоритма ===
+
==Неправильные способы реализации==
Общей ошибкой при реализации тасования Фишера – Йетса является выбор случайных чисел из неверного интервала.
+
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.  
Дефектный алгоритм может казаться работающим корректно, но он не создает все возможные перестановки с равной вероятностью, а некоторые перестановки может вообще не создать.
 
Например, общая ошибка занижения или завышения на единицу может возникнуть при выборе индекса ''j'' переставляемого элемента в [[#Современный алгоритм|примере выше]] всегда меньше индекса ''i'', с которым элемент должен быть переставлен.
 
В результате вместо тасования Фишера-Йета получим алгоритм Саттоло, который образует перестановки, затрагивающие все элементы. В частности, в этом случае никакой элемент не может оказаться на начальной позиции.
 
  
[[Файл:Probabilities7.png|200px|thumb|right|Вероятность того, что элемент i окажется на позиции j при неверной реализации алгоритма]]
+
===Пример неправильной реализации:===
 +
  '''for''' i = n '''downto''' 1
 +
    swap(a[i], a[random(1..n)])
 +
В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, в то время как существует всего <tex> n!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку <tex> n^n</tex> никогда не может делиться на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.
  
Подобным образом, выбор ''j'' из всех индексов в массиве на каждой итерации также образует неравновероятные перестановки, хотя и не столь очевидно.
+
===Другой пример неправильной реализации:===
Это можно установить из того факта, что такая реализация образует ''n''<sup>''n''</sup> различных обменов местами для элементов, в то время как существует всего [[Факториал|''n''!]] возможных перестановок массива из ''n'' элементов.
+
  '''for''' i = n '''downto''' 1
Поскольку ''n''<sup>''n''</sup> никогда не может делиться на ''n''!  без остатка при  ''n'' &gt; 2 (поскольку ''n''! делится на число ''n''−1, которое не имеет с ''n'' общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.
+
    swap(a[random(1..n)], a[random(1..n)])
Рассмотрим конкретный пример перестановок трех элементов [1, 2, 3]. Имеется 6 возможных перестановок этого набора (3! = 6), но алгоритм образует 27 перетасовок (3<sup>3</sup> = 27).  В этом случае [1, 2, 3], [3, 1, 2], и [3, 2, 1] встречаются по 4 раза в 27 перетасовках, в то время как оставшиеся 3 встречаются по 5 раз.
 
  
Матрица справа показывает вероятность появления каждого элемента из списка длины 7 в конечной позиции. Заметьте, что для большинства элементов остаться при тасовании на своей начальной позиции (главная диагональ матрицы) имеет минимальную вероятность, а сдвинуться на одну позицию влево - максимальную.
+
Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на  <tex> n!</tex> без остатка при <tex> n > 2</tex>, следовательно некоторые перестановки будут появляться еще чаще.
  
=== Нарушение равномерности распределения при взятии по модулю ===
+
==См.также==
 
+
*[[Методы генерации случайного сочетания | Методы генерации случайного сочетания]]
Алгоритм Фишера-Йетса использует выборку равномерно распределенных случайных чисел из различных диапазонов. Большинство генераторов случайных чисел, однако, как настоящих случайных, так и псевдослучайных дают числа в фиксированном диапазоне, скажем от 0 до 2<sup>32</sup>−1.
+
==Источники информации==
Простой и обычно используемый метод приведения таких чисел к нужному интервалу заключается в использовании сравнения по модулю, то есть, взятия остатка от деления на верхнюю границу.  Необходимость генерировать случайные числа во всех интервалах от 0–1 до 0–''n'' гарантирует, что некоторые из этих границ не будут делить естественную границу генератора нацело.
+
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
Как результат, распределение не будет равномерным и маленькие остатки будут встречаться чаще.
 
 
 
Предположим, например, что генератор дает случайные числа между 0 и 99 (как было у Фишера и Йетса в их оригинальных таблицах), а вы хотите получить случайные числа между 0 и 15.  Если вы просто находите остаток числа при делении на 16, вы обнаружите, что числа 0–3 встречаются на 17% чаще, чем остальные.  Причина этого заключается в том, что 16 не делит 100 нацело – наибольшее число, кратное 16 и не превышающее 100 есть 6×16 = 96, а оставшиеся числа из диапазона 96–99 создают неравномерность. Самый простой способ избежать этой проблемы заключается в отбрасывании таких чисел до взятия остатка. Хотя, в принципе, числа из такого интервала могут попадаться, математическое ожидание числа повторных попыток всегда меньше единицы.
 
 
 
Похожая проблема возникает в случае использования генератора случайных чисел, дающего числа с плавающей запятой, обычно в диапазоне [0,1). Полученное число умножают на размер желаемого диапазона и округляют.  Проблема здесь в том, что даже аккуратно сгенерированные случайные числа с плавающей запятой имеют конечную точность, что означает, что можно получить только конечное число возможных чисел с плавающей запятой, и, как и в случае выше, эти числа разбиваются на сегменты, которые не делят число нацело и некоторые сегменты получают большую вероятность появления, чем другие.
 
=== Псевдослучайные генераторы: проблему, обусловленные внутренними состояниями генератора случайных чисел, начальными параметрами и использованием ===
 
 
 
Дополнительные проблемы появляются при использовании генератора псевдослучайных чисел (ГПСЧ).
 
Генерация псевдослучайной последовательности таких генераторов полностью определяется их внутренним состоянием в начале генерации.
 
Программа тасования, опирающаяся на такой генератор, не может создать больше перестановок, чем число внутренних состояний генератора. Даже когда число возможных состояний генератора перекрывает число перестановок, некоторые перестановки могут появляться чаще, чем другие. Во избежание появления  неравномерности распределения число внутренних состояний генератора случайных чисел должно превосходить число перестановок на несколько порядков.
 
 
 
Например, встроенный генератор псевдослучайных чисел, имеющийся во многих языках программирования и библиотеках использует, обычно, 32-битное число для внутренних состояний, что означает, что такой генератор может создать только 2<sup>32</sup> различных случайных чисел.  Если такой генератор будет использоваться для тасования колоды из 52 игральных карт, он может может создать очень маленькую часть от [[Факториал|52!]] ≈ 2<sup>225.6</sup> возможных перестановок.  Генератор с менее чем 226-битным числом внутренних состояний не может создать все перестановки колоды из 52 игральных карт.  Считается, что для создания равномерного распределения необходим генератор, имеющий не менее 250-битного числа состояний.
 
 
 
Естественно, что никакой генератор псевдослучайных чисел не может создать больше случайных последовательностей, задающихся различными начальными данными, чем число этих начальных данных. Так, генератор с 1024-битным числом внутренних состояний, для которого задаются 32-битные начальные параметры, может создать лишь 2<sup>32</sup> различных последовательностей перестановок. Можно получить больше перестановок, выбирая достаточно много случайных чисел из генератора до начала его использования в алгоритме тасования, но такой подход очень неэффективен – выборка, скажем,  2<sup>30</sup> случайных чисел до использования последовательности в алгоритме тасования повышает число перестановок только до 2<sup>62</sup>.
 
 
 
Ещё одна проблема появляется при использовании простого линейного конгруэнтного ГПСЧ, когда для уменьшения интервала случайных чисел используется остаток от деления, как было указано выше. Проблема здесь в том, что младшие биты линейного конгруэнтного ГПСЧ менее случайны по сравнению со старшими битами – младшие ''n'' бит имеют период максимум 2<sup>''n''</sup>.  Если делитель является степенью двойки, взятие остатка означает отбрасывание старших битов, что приводит к существенному уменьшению случайности. 
 
 
 
Наконец, следует заметить, что даже использование прекрасного генератора, изъян в алгоритме может возникнуть из-за неправильного использования генератора. Представим себе, например,  что реализация алгоритма на языке Java создает новый генератор для каждого вызова процесса тасования без задания параметров в конструкторе. Для инициализации генератора будет использовано текущее время  (System.currentTimeMillis()).  Таким образом, два вызова с разницей во времени менее миллисекунды дадут идентичные перестановки. Это случится почти наверняка, если тасование происходит многократно и быстро, что приведет к крайне неравномерному распределению перестановок. Такая же проблема может возникнуть при получении случайных чисел из двух различных потоков.  Правильнее использовать один статический экземпляр генератора, определенный вне процедуры тасования.
 
 
 
==Примечание==
 
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Йетс (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
 
*Д.Э. Кнут Искусство программирования, том 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 Википедия — Тасование Фишера-Йетса]
*[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 Википедия - Тасование Фишера–Йетса]
+
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
 
 
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]
 +
 +
[[Категория: Генерация комбинаторных объектов]]

Версия 09:30, 21 февраля 2018

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

Применение алгоритма

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

Решение:

Пусть

  • [math]\mathtt{random(1..i) }[/math] генерирует случайное число в отрезке [math] [1;\; i] [/math]

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

 int[n] randomPermutation(a: int[n]):   // n — длина перестановки 
   for i = n downto 1
     j = random(1..i)
     swap(a[i], a[j])
   return a

Обоснование

На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть [math] n[/math] способов выбрать [math]1[/math] элемент, [math] n - 1[/math] способов выбрать [math]2[/math] элемент... [math] 1[/math] способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины [math] n[/math] мы можем получить [math] n \times (n - 1) \times \ldots \times 1 = n! [/math] способами, что совпадает с числом различных перестановок длины [math] n[/math]. Это означает, что вероятность выбрать любую перестановку длины [math] n[/math] равна [math] \dfrac{1}{n!}[/math], то есть все перестановки равновероятны.

Неправильные способы реализации

Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

Пример неправильной реализации:

 for i = n downto 1
   swap(a[i], a[random(1..n)])

В данном случае число способов сгенерировать последовательность равно [math]n^n[/math], в то время как существует всего [math] n![/math] возможных перестановок из [math] n[/math] элементов. Поскольку [math] n^n[/math] никогда не может делиться на [math] n![/math] без остатка при [math] n \gt 2[/math] (так как [math] n![/math] делится на число [math] n - 1[/math] , которое не имеет с [math] n[/math] общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

Другой пример неправильной реализации:

 for i = n downto 1
   swap(a[random(1..n)], a[random(1..n)])

Теперь уже число способов сгенерировать последовательность равно [math](n^2)^n[/math]. По той же причине, что и раньше [math] (n^2)^n[/math] не делится на [math] n![/math] без остатка при [math] n \gt 2[/math], следовательно некоторые перестановки будут появляться еще чаще.

См.также

Источники информации