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