Изменения

'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>.==Постановка задачиПрименение алгоритма=={{Задача|definition = Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии есть функция для генерации случайного числа в заданном интервале. }}===Решение:=== 

*''<tex>\mathtt{random(1..i);'' }</tex> генерирует случайное число в интервале отрезке <tex> [1;\; i] </tex> <br/>*''swap(i, j);'' меняет местами числа на местах i и j в массиве <tex> a[\;]</tex><br/>*и пусть для определенности массив задан: <tex> a[\;] = \langle 1, 2, 3, ..., (n-1), n\rangle </tex> <br/>

Этот алгоритм носит имя Фишера '''int[n]''' randomPermutation(a: '''int[n]'''): <font color = green> // '''n''' {{-Йетса--}} длина перестановки </font> '''for''' i = n '''downto''' 1 j = random(1..i) swap(a[i], a[j]) '''return''' a 

Проведем доказательство по индукции. Всего перестановок <tex> n! </tex>, поэтому вероятность На каждой итерации цикла мы выбираем случайный элемент из них должна быть равна всех оставшихся, то есть у нас есть <tex> \frac {1}{n!}</tex>. Показажем, что на каждом i-ом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.* при способов выбрать <tex> i = 1 </tex> перестановка всего однаэлемент, и, очевидно, что база верна* пусть при <tex> i = k - 1 </tex> каждая перестановка первых i элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки на in -ом шаге цикла равна <tex> \frac {1}{(k-1)!}</tex>: при способов выбрать <tex> i = k 2</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}n</tex> останется мы можем получить <tex> n \frac {1}{times (kn -1)\times \ldots \times 1 = n!} </tex>способами, что в результате дает, что вероятность перестановки первых k элементов равна совпадает с числом различных перестановок длины <tex> \frac {1}{k!}n</tex><br/>Другой способ обоснования заключается в том. Это означает, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за вероятность выбрать любую перестановку длины <tex> n </tex> шагов, таким образом автоматически получается, что все равна <tex> \dfrac{1}{n!}</tex> перестановок , то есть все перестановки равновероятны.<br/>

Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно ===Пример неправильной реализации:=== '''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(ia[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] [[Категория: Дискретная математика и алгоритмы]]

В самом деле[[Категория: число способов сгенерировать последовательность в первом случае равно <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/>*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>==Литература==*Дональд Кнут Искусство программирования, том 2. Получисленные методы = The Art of Computer Programming, vol.2. Seminumerical Algorithms. — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2Генерация комбинаторных объектов]]