39
правок
Изменения
м
→Обоснование
==Обоснование==
Проведем доказательство по индукции. Всего перестановок <tex> n! </tex>, поэтому вероятность каждой из них должна быть равна <tex> \frac {1}{n!}</tex>. Показажем, что на каждом <tex>i</tex>-ом шаге цикла любая перестановка из первых <tex>i</tex> элементов равновероятна.
* при <tex> i = 1 </tex> перестановка всего одна, и, очевидно, что база верна
* пусть при <tex> i = k - 1 </tex> каждая перестановка первых <tex>i</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>k</tex>-ом месте равна <tex>\frac{1}{k}</tex>. Вероятность же какой-то перестановки первых <tex>(k-1)</tex> элементов при известном <tex>a_{k}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность перестановки первых <tex>k</tex> элементов равна <tex> \frac {1}{k!}</tex>
<br/>
