Случайная перестановка — это случайное упорядочение множества объектов, то есть случайная величина, элементарными событиями которой являются перестановки. Использование случайных перестановок зачастую является базой в областях, использующих рандомизированные алгоритмы. К таким областям относятся теория кодирования, криптография и моделирование. Хорошим примером случайной перестановки является тасование колоды карт.
Прямой метод (элемент за элементом)
Одним из методов генерации случайной перестановки множества из n элементов является использование равномерного распределения, для чего выбираются последовательно случайные числа между 1 и n, обеспечивая при этом отсутствие повторений. Полученная последовательность (x1, …, xn) интерпретируется как перестановка
Прямой метод генерации требует повторения выбора случайного числа, если выпавшее число уже есть в последовательности. Этого можно избежать, если на i-м шаге (когда x1, …, xi − 1 уже выбраны), выбирать случайное число j между 1 и n − i + 1 и, затем, выбирать xi, равным j-му невыбранному числу.
Тасование Кнута
Простой алгоритм генерации случайных перестановок из n элементов (с равномерным распределением) без повторов, известный как тасование Кнута, начинается с произвольной перестановки (например, с тождественной — без перестановки элементов), и проходит с позиции 1 до позиции n − 1, переставляя элемент на позиции i со случайно выбранным элементом на позициях от i до n включительно. Легко показать, что таким способом мы получим все перестановки n элементов с вероятностью в точности 1/n!.
Неподвижные точки
Распределение вероятностей числа неподвижных точек в равномерно распределенных случайных перестановках на n элементах приближается к закону Пуассона при росте n. Подсчет числа неподвижных точек является классическим примером использования формулы включений-исключений, которая показывает, что вероятность отсутствия неподвижных точек приближается к 1/e. При этом математическое ожидание числа неподвижных точек равно 1 при любом размере перестановки.[1]
Как и во всех других случайных процессах, качество алгоритма генерации перестановок, в частности, алгоритма тасования Кнута, зависит от положенного в основание генератора случайных чисел, такого как генератор псевдослучайных чисел. Имеется большое число возможных тестов случайности, например, тесты diehard. Типичный пример такого теста заключается в выборе некоторой статистики, для которой распределение известно, и проверить, действительно ли распределение этой статистики на множестве полученных перестановок достаточно близко к настоящему распределению.
- Постоянная Голомба — Дикмана
- Алгоритмы тасования — метод случайной сортировки, метод итеративных перестановок
- Случайная перестановка
- Криптоанализ LEX
- Задача о 100 узниках и 100 ящиках
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
