Главная
Новости
Строительство
Ремонт
Дизайн и интерьер
Полезные советы



















Яндекс.Метрика





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

Случайная перестановка — это случайное упорядочение множества объектов, то есть случайная величина, элементарными событиями которой являются перестановки. Использование случайных перестановок зачастую является базой в областях, использующих рандомизированные алгоритмы. К таким областям относятся теория кодирования, криптография и моделирование. Хорошим примером случайной перестановки является тасование колоды карт.

Генерация случайных перестановок

Прямой метод (элемент за элементом)

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

( 1 2 3 ⋯ n x 1 x 2 x 3 ⋯ x n ) , {displaystyle {egin{pmatrix}1&2&3&cdots &nx_{1}&x_{2}&x_{3}&cdots &x_{n}end{pmatrix}},}

Прямой метод генерации требует повторения выбора случайного числа, если выпавшее число уже есть в последовательности. Этого можно избежать, если на i-м шаге (когда x1, …, xi − 1 уже выбраны), выбирать случайное число j между 1 и ni + 1 и, затем, выбирать xi, равным j-му невыбранному числу.

Тасование Кнута

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

Статистика на случайных перестановках

Неподвижные точки

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

Проверка случайности

Как и во всех других случайных процессах, качество алгоритма генерации перестановок, в частности, алгоритма тасования Кнута, зависит от положенного в основание генератора случайных чисел, такого как генератор псевдослучайных чисел. Имеется большое число возможных тестов случайности, например, тесты diehard. Типичный пример такого теста заключается в выборе некоторой статистики, для которой распределение известно, и проверить, действительно ли распределение этой статистики на множестве полученных перестановок достаточно близко к настоящему распределению.


Имя:*
E-Mail:
Комментарий: