Случайная перестановка

Одним из методов генерации случайной перестановки множества из n элементов является использование равномерного распределения, для чего выбираются последовательно случайные числа между 1 и n, обеспечивая при этом отсутствие повторений. Полученная последовательность (x₁, …, x_n) интерпретируется как перестановка

${\displaystyle {\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},}$

Прямой метод генерации требует повторения выбора случайного числа, если выпавшее число уже есть в последовательности. Этого можно избежать, если на i-м шаге (когда x₁, …, x_{i − 1} уже выбраны), выбирать случайное число j между 1 и n − i + 1 и, затем, выбирать x_i, равным j-му невыбранному числу.

Простой алгоритм генерации случайных перестановок из n элементов (с равномерным распределением) без повторов, известный как тасование Кнута, начинается с произвольной перестановки (например, с тождественной — без перестановки элементов), и проходит с позиции 1 до позиции n − 1, переставляя элемент на позиции i со случайно выбранным элементом на позициях от i до n включительно. Легко показать, что таким способом мы получим все перестановки n элементов с вероятностью в точности 1/n!.

Распределение вероятностей числа неподвижных точек в равномерно распределенных случайных перестановках на n элементах приближается к закону Пуассона при росте n. Подсчет числа неподвижных точек является классическим примером использования формулы включений-исключений, которая показывает, что вероятность отсутствия неподвижных точек приближается к 1/e. При этом математическое ожидание числа неподвижных точек равно 1 при любом размере перестановки.[1]