Изменения

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

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

  function '''int[n]''' randomPermutation(a:array'''int[1..n] of integer'''):array[1..n] of integer <font color = green> // '''n — ''' {{---}} длина массиваперестановки </font> '''for ''' i = n '''downto''' 1 to n j = <tex>\mathrm{random(1..i)}</tex> <tex>\mathrm{swap(a[i], a[j])}</tex> '''return ''' a

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

===Пример неправильной реализации:=== '''for ''' i = n '''downto''' 1..n 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^2)^n</tex>, а всего последовательностей не делится на <tex> n!</tex>. Для того, чтобы сгенерированные последовательности были равновероятны, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо без остатка при <tex>(n^n) \vdots n!</tex> а во втором случае <tex>((n^2)^n) \vdots n!</tex>, что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3следовательно некоторые перестановки будут появляться еще чаще.

*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2*[httphttps://neercru.ifmowikipedia.ruorg/wiki/index.php?title=%D0%9CA2%D0%B5B0%D1%8281%D0%BE%D0%B4%D1%8B_B2%D0%B3B0%D0%B5BD%D0%BDB8%D0%B5%D1%80B5_%D0%B0%D1%86A4%D0%B8%D0%B8_%D1%8188%D0%BBB5%D1%83%D1%8780%D0%B0%D0E2%B980%D0%BD93%D0%BE99%D0%B3B5%D0D1%BE_82%D1%81%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D1%8F Методы генерации случайного сочетанияВикипедия — Тасование Фишера-Йетса]*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]