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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Решение)
(Обоснование)
(не показана 21 промежуточная версия 3 участников)
Строка 1: Строка 1:
'''Тасование Фишера–Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.   
+
'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.   
Основная процедура тасования Фишера–Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
+
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>.
 +
==Применение алгоритма==
 +
{{Задача
 +
|definition = Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.
 +
}}
 +
===Решение:===
  
==Постановка задачи==
 
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
 
==Решение==
 
 
Пусть <br/>
 
Пусть <br/>
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
+
*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в отрезке <tex> [1;\; i] </tex> <br/>
 
Следующий алгоритм решает задачу:
 
Следующий алгоритм решает задачу:
   '''int *a''' randomPermutation('''int *a''') // '''*a''' - указатель на массив типа '''int''' длины '''n'''
+
 
     '''for''' i = n '''to''' 1
+
   '''int[n]''' randomPermutation(a: '''int[n]'''):  <font color = green> // '''n''' {{---}} длина перестановки </font>
 +
     '''for''' i = n '''downto''' 1
 
       j = random(1..i)
 
       j = random(1..i)
 
       swap(a[i], a[j])
 
       swap(a[i], a[j])
  return a
+
    '''return''' a
  
 
==Обоснование==
 
==Обоснование==
Проведем доказательство по индукции. Всего перестановок <tex> n! </tex>, поэтому вероятность каждой из них должна быть равна <tex> \frac {1}{n!}</tex>. Показажем, что на каждом <tex>i</tex>-ом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.
+
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <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>, то есть все перестановки равновероятны.
* при <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 = \{ 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/>
 
  
 
==Неправильные способы реализации==
 
==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно:
+
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.  
  '''for''' i = 1 '''to''' n
 
    swap(i, random(1..n))
 
  
   '''for''' i = 1 '''to''' n
+
===Пример неправильной реализации:===
     swap(random(1..n), random(1..n))
+
   '''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> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.
  
В самом деле: число способов сгенерировать последовательность в первом случае равно <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> общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие. Аналогично для второго случая, где число способов сгенерировать последовательность равно уже <tex> (n^2)^n</tex>.
+
===Другой пример неправильной реализации:===
 +
  '''for''' i = n '''downto''' 1
 +
    swap(a[random(1..n)], a[random(1..n)])
 +
 
 +
Теперь уже число способов сгенерировать последовательность равно <tex>(n^2)^n</tex>. По той же причине, что и раньше <tex> (n^2)^n</tex> не делится на <tex> n!</tex> без остатка при <tex> n > 2</tex>, следовательно некоторые перестановки будут появляться еще чаще.
  
==Примечание==
 
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Йетс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
 
*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>
 
 
==См.также==
 
==См.также==
 +
*[[Методы генерации случайного сочетания | Методы генерации случайного сочетания]]
 +
==Источники информации==
 
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
 
*[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 Методы генерации случайного сочетания]
 
==Источники информации==
 
 
*Д.Э. Кнут Искусство программирования, том 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]
+
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia Fisher-Yates 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], следовательно некоторые перестановки будут появляться еще чаще.

См.также

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