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

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

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

Одним из методов генерации случайной перестановки множества из 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 при любом размере перестановки.

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

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

См. также

• Постоянная Голомба — Дикмана
• Алгоритмы тасования — метод случайной сортировки, метод итеративных перестановок
• Случайная перестановка
• Криптоанализ LEX
• Задача о 100 узниках и 100 ящиках

Примечания

Литература

• Jim Pitman. Probability. — Springer Science & Business Media, 2012. — P. 153–. — ISBN 978-1-4612-4374-8 .
• В. Г. Потемкин «Справочник по MATLAB» Работа с разреженными матрицами. Описано использование процедуры randperm генерации случайных перестановок в пакете MathLab.
• Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 2003. — С. 129-130. — ISBN 0-201-00023-7 / 5-8459-0122-7.
• Альфред В Ахо, Джон Э Хопкрофт, Джеффри Д Ульман. Алгоритмы. Построение и анализ. — Санкт-Петербург, Москва, Киев: Издательский дом "Вильямс", 2007. — С. 152-153 Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
• Арнольд В.И. . — М. : МЦНМО, 2006. — С. -84. — (Летняя школа «Современная математика»). — ISBN 978-5-94057-282-4 .
• Т. Кристиансен,Н. Торкингтон. Perl. Библиотека программиста. — Питер, 2001. — С. В главе 4 "Массивы" рассматривается все, что относится к операциям со списками и массивами, в том числе поиск уникальных элементов, эффективная сортировка и случайные перестановки элементов.. — ISBN 5-8046-0094-X .
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. . — М. : "Вильямc", 2005. — С. Глава 5.3 Рандомизированные алгоритмы. — ISBN 5-8459-0857-4 .
• Борис Николаевич Иванов. Дискретная математика. Алгоритмы и программы. Расширенный курс. — М. : Известия, 2011. — С. 180, Случайные перестановки. — ISBN 978-5-206-00824-1 .
• И.В. Красиков, И.Е. Красиков. Алгоритмы. Просто как дважды два. — М. : Эксмо, 2007. — ISBN 978-5-699-21047-3 .
• Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие. Просто как дважды два. — М. : Лаборатория Базовых Знаний, 2003. — С. 89. 4.8 Генерация случайных перестановок. — (Технический университет). — ISBN 5-93208-093-0 .

Ссылки

• на MathWorld
• — детальное изложение алгоритма тасования Кнута и его вариантов для генерации перестановок k -перестановок (перестановок k элементов, выбранных из списка) и k -подмножеств
• Герасимов Василий Александрович. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру.