223
правки
Изменения
Нет описания правки
Этот алгоритм носит имя Фишера-Йетса.
==Обоснование==
Проведем его доказательство по индукции. Требуется доказать, что на каждом шаге цикла каждая перестановка равновероятна.
* при <tex> n = 1 </tex> перестановка всего одна, и, очевидно, что база верна
* пусть при <tex> n = k - 1 </tex> каждая перестановка равновероятна, то есть вероятность отдельно взятой перестановки <tex> \frac {1}{(k-1)!}</tex>
