Изменения

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

*<tex>\mathtt{random(1..i) }</tex> генерирует случайное число в интервале отрезке <tex> [1;\; i] </tex> <br/>

  '''int *a[n]''' randomPermutation(a: '''int *a[n]''') : <font color = green> // '''*an''' {{--- указатель на массив типа '''int''' длины '''n'''}} длина перестановки </font> '''for''' i = n '''todownto''' 1

'''return ''' a

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

Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например, следующие два алгоритма работают неправильно: '''for''' i = 1 '''to''' n swap(i, random(1..n))

===Пример неправильной реализации:=== '''for''' i = 1 n '''todownto''' n1 swap(a[i], a[random(1..n)])В данном случае число способов сгенерировать последовательность равно <tex>n^n</tex>, randomв то время как существует всего <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!</tex> возможных перестановок из <tex> n</tex> элементов. Поскольку что и раньше <tex> (n^2)^n</tex> никогда не может делиться делится на <tex> n!</tex> без остатка при <tex> n > 2</tex> (так как <tex> n!</tex> делится на число <tex> n - 1</tex> , которое не имеет с <tex> n</tex> общих простых делителей), то следовательно некоторые перестановки должны будут появляться еще чаще, чем другие. Аналогично для второго случая, где число способов сгенерировать последовательность равно уже <tex> (n^2)^n</tex>.

*[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]