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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
==Решение==
 
==Решение==
 
Пусть <br/>
 
Пусть <br/>
−
*''random(1..i);'' генерирует случайное число в интервале <tex> [1; i] </tex> <br/>
+
*''random(1..i);'' генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
 
*''swap(i, j);'' меняет местами числа на местах i и j  в массиве <tex> a[\;]</tex><br/>
 
*''swap(i, j);'' меняет местами числа на местах i и j  в массиве <tex> a[\;]</tex><br/>
−
*и пусть для определенности массив задан: <tex> a[\;] = <1, 2, 3, ..., (n-1), n> </tex> <br/>
+
*и пусть для определенности массив задан: <tex> a[\;] = \langle 1, 2, 3, ..., (n-1), n\rangle </tex> <br/>
 
Следующий алгоритм решает задачу:
 
Следующий алгоритм решает задачу:
 
   for i = 1..n
 
   for i = 1..n
Строка 12: Строка 12:
 
Этот алгоритм носит имя Фишера-Йетса.
 
Этот алгоритм носит имя Фишера-Йетса.
 
==Обоснование==
 
==Обоснование==
−
Проведем доказательство по индукции. Требуется доказать, что на каждом шаге цикла каждая перестановка равновероятна.
+
Проведем доказательство по индукции. Требуется доказать, что на каждом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.
−
* при <tex> n = 1 </tex> перестановка всего одна, и, очевидно, что база верна
+
* при <tex> i = 1 </tex> перестановка всего одна, и, очевидно, что база верна
−
* пусть при <tex> n = k - 1 </tex> каждая перестановка равновероятна, то есть вероятность отдельно взятой перестановки <tex> \frac {1}{(k-1)!}</tex>
+
* пусть при <tex> i = k - 1 </tex> каждая перестановка первых i элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки на i-ом шаге цикла равна <tex> \frac {1}{(k-1)!}</tex>
−
: <tex> a[\;] = <a_{1}, a_{2}, ..., a_{n-1}, n> </tex>
+
: при <tex> i = k </tex>:
−
: после swap(i, random(1..i)) вероятность какого-то числа оказаться на n-ом месте равна <tex>\frac{1}{n}</tex>, вероятность же какой-то последовательности чисел до n-ого элемента при известном <tex>a_{n}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность всей перестановки <tex> \frac {1}{k!}</tex>
+
: <tex> a[\;] = \langle a_{1}, a_{2}, ..., a_{k-1}, k, ... \rangle </tex>
 +
: после swap(i, random(1..i)) вероятность какого-то числа оказаться на k-ом месте равна <tex>\frac{1}{k}</tex>, вероятность же какой-то перестановки первых (k-1) элементов при известном <tex>a_{k}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность перестановки первых k элементов равна <tex> \frac {1}{k!}</tex>
 
<br/>
 
<br/>
 
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex> шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
 
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex> шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
  
 
==Неправильные способы реализации==
 
==Неправильные способы реализации==
−
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например следующие два алгоритма работают неправильно:
+
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно:
 
   for i = 1..n
 
   for i = 1..n
 
     swap(i, random(1..n))
 
     swap(i, random(1..n))
Строка 28: Строка 29:
 
     swap(random(1..n), random(1..n))
 
     swap(random(1..n), random(1..n))
  
−
В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно <tex>n^n</tex>, во втором равно <tex> (n^2)^n</tex>, а всего последовательностей <tex> n!</tex>. Для того, чтобы сгенерированная последовательность была случайной, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо <tex>(n^n) \vdots n!</tex> а во втором случае <tex>((n^2)^n) \vdots n!</tex>, что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3.
+
В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно <tex>n^n</tex>, во втором равно <tex> (n^2)^n</tex>, а всего последовательностей <tex> n!</tex>. Для того, чтобы сгенерированные последовательности были равновероятны, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо <tex>(n^n) \vdots n!</tex> а во втором случае <tex>((n^2)^n) \vdots n!</tex>, что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3.
 
==Примечание==
 
==Примечание==
 
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
 
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>

Версия 23:03, 15 января 2011

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

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

Решение

Пусть

  • random(1..i); генерирует случайное число в интервале [math] [1;\; i] [/math]
  • swap(i, j); меняет местами числа на местах i и j в массиве [math] a[\;][/math]
  • и пусть для определенности массив задан: [math] a[\;] = \langle 1, 2, 3, ..., (n-1), n\rangle [/math]

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

 for i = 1..n
   swap(i, random(1..i))

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

Обоснование

Проведем доказательство по индукции. Требуется доказать, что на каждом шаге цикла любая перестановка из первых [math]i[/math] элементов равновероятна.

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


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

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

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

 for i = 1..n
   swap(i, random(1..n))

 for i = 1..n
   swap(random(1..n), random(1..n))

В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно [math]n^n[/math], во втором равно [math] (n^2)^n[/math], а всего последовательностей [math] n![/math]. Для того, чтобы сгенерированные последовательности были равновероятны, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо [math](n^n) \vdots n![/math] а во втором случае [math]((n^2)^n) \vdots n![/math], что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3.

Примечание

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

Литература

  • Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Метод_генерации_случайной_перестановки,_алгоритм_Фишера-Йетса&oldid=6968»