39
правок
Изменения
Нет описания правки
'''Тасование Фишера–ЙетсаФишера – Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) – {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера–Йетса Фишера – Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.Время работы алгоритма <tex> O(n)</tex>
==Постановка задачи==
Следующий алгоритм решает задачу:
'''int[]''' randomPermutation('''int[] a''') <font color = green> // '''n''' {{- --}} длина перестановки </font>
'''for''' i = n '''downto''' 1
j = random(1..i)
==Обоснование==
Корректность данного алгоритма очевидна. На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть <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> \fracdfrac{1}{n!}</tex>, то есть все перестановки равновероятны.
==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно:
'''for''' i = n '''todownto''' 1
swap(i, random(1..n))
'''for''' i = n '''todownto''' 1
swap(random(1..n), 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^2)^n</tex>.
==См.также==
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]
