223
правки
Изменения
Новая страница: «==Постановка задачи== Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с …»
==Постановка задачи==
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
==Решение==
Пусть <br/>
*''random(1..i);'' генерирует случайное число в интервале <tex> [1; i] </tex> <br/>
*''swap(i, j);'' меняет местами числа на местах i и j в массиве <tex> a[\;]</tex><br/>
*и пусть для определенности массив задан: <tex> a[\;] = <1, 2, 3, ..., (n-1), n> </tex> <br/>
Следующий алгоритм решает задачу:
for i = 1..n
swap(i, random(1..i))
==Обоснование==
Проведем его по индукции. Требуется доказать, что на каждом шаге цикла каждая перестановка равновероятна.
* при <tex> n = 1 </tex> перестановка всего одна, и, очевидно, что база верна
* пусть при <tex> n = k - 1 </tex> каждая перестановка равновероятна, то есть вероятность отдельно взятой перестановки <tex> \frac {1}{(k-1)!}</tex>
: <tex> a[\;] = <a_{1}, a_{2}, ..., a_{n-1}, n> </tex>
: после swap(i, random(1..i)) вероятность какого-то числа оказаться на n-ом месте равна <tex>\frac{1}{n}</tex>, вероятность же какой-то последовательности чисел до n-ого элемента при известном <tex>a_{n}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность всей перестановки <tex> \frac {1}{k!}</tex>
<br/>
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex> шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например следующие два алгоритма работают неправильно:
for i = 1..n
swap(i, random(1..n))
for i = 1..n
swap(random(1..n), random(1..n))
В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно <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>,что заведомо не выполняется при подстановке любого нечетного числа.
==Примечание==
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.
==Решение==
Пусть <br/>
*''random(1..i);'' генерирует случайное число в интервале <tex> [1; i] </tex> <br/>
*''swap(i, j);'' меняет местами числа на местах i и j в массиве <tex> a[\;]</tex><br/>
*и пусть для определенности массив задан: <tex> a[\;] = <1, 2, 3, ..., (n-1), n> </tex> <br/>
Следующий алгоритм решает задачу:
for i = 1..n
swap(i, random(1..i))
==Обоснование==
Проведем его по индукции. Требуется доказать, что на каждом шаге цикла каждая перестановка равновероятна.
* при <tex> n = 1 </tex> перестановка всего одна, и, очевидно, что база верна
* пусть при <tex> n = k - 1 </tex> каждая перестановка равновероятна, то есть вероятность отдельно взятой перестановки <tex> \frac {1}{(k-1)!}</tex>
: <tex> a[\;] = <a_{1}, a_{2}, ..., a_{n-1}, n> </tex>
: после swap(i, random(1..i)) вероятность какого-то числа оказаться на n-ом месте равна <tex>\frac{1}{n}</tex>, вероятность же какой-то последовательности чисел до n-ого элемента при известном <tex>a_{n}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность всей перестановки <tex> \frac {1}{k!}</tex>
<br/>
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex> шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
==Неправильные способы реализации==
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. Например следующие два алгоритма работают неправильно:
for i = 1..n
swap(i, random(1..n))
for i = 1..n
swap(random(1..n), random(1..n))
В самом деле: в первом случае число способов сгенерировать последовательность в первом случае равно <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>,что заведомо не выполняется при подстановке любого нечетного числа.
==Примечание==
*Впервые этот алгоритм опубликовали Р.А.Фишер и Ф.Ятс (R.A.Fisher and F. Yates, Statistical Tables (London 1938), Example 12).<br/>
*Нетрудно увидеть, что сложность алгоритма <tex> O(n)</tex>
