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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Источники)
Строка 41: Строка 41:
 
*[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 Методы генерации случайного сочетания]
 
*[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
 +
*[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]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
  
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Версия 15:10, 22 января 2016

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

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

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

Решение

Пусть

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

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

 int *a randomPermutation(int *a) // *a - указатель на массив типа int длины n
   for i = 1 to n
     j = random(1..i)
     swap(a[i], a[j])
 return a

Обоснование

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

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

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

 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]

См.также

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