Изменения

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

*и пусть для определенности массив задан: <tex> a[\;] = <\langle 1, 2, 3, ..., (n-1), n> \rangle </tex> <br/>

Проведем доказательство по индукции. Требуется доказать, что на каждом шаге цикла каждая любая перестановка из первых <tex>i</tex> элементов равновероятна.* при <tex> n i = 1 </tex> перестановка всего одна, и, очевидно, что база верна* пусть при <tex> n i = k - 1 </tex> каждая перестановка первых i элементов равновероятна, то есть вероятность каждой отдельно взятой перестановки на i-ом шаге цикла равна <tex> \frac {1}{(k-1)!}</tex>: при <tex> i = k </tex>:: <tex> a[\;] = <\langle a_{1}, a_{2}, ..., a_{nk-1}, n> k, ... \rangle </tex>: после swap(i, random(1..i)) вероятность какого-то числа оказаться на nk-ом месте равна <tex>\frac{1}{nk}</tex>, вероятность же какой-то последовательности чисел до nперестановки первых (k-ого элемента 1) элементов при известном <tex>a_{nk}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность всей перестановки первых k элементов равна <tex> \frac {1}{k!}</tex>

Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например , следующие два алгоритма работают неправильно:

В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно <tex>n^n</tex>, во втором равно <tex> (n^2)^n</tex>, а всего последовательностей <tex> n!</tex>. Для того, чтобы сгенерированная последовательность была случайнойсгенерированные последовательности были равновероятны, необходимо хотя бы, чтобы число способов получить последовательность было кратно их общему числу. То есть в первом случае необходимо <tex>(n^n) \vdots n!</tex> а во втором случае <tex>((n^2)^n) \vdots n!</tex>, что заведомо не выполняется при подстановке любого нечетного числа, начиная с 3.