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