Випадкова перестановка

Випадкова перестановка — це випадкове впорядкування множини об'єктів, тобто випадкова величина, елементарними подіями якої є перестановки. Випадкові перестановки часто застосовують у галузях, які використовують увипадковлені алгоритми: теорії кодування, криптографії, моделюванні тощо. Прикладом випадкової перестановки є тасування колоди карт.

Генерування випадкових перестановок

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

Одним з методів генерування випадкової перестановки множини з $n$ елементів є використання рівномірного розподілу, для чого вибирають послідовно випадкові числа між 1 і $n$, забезпечуючи при цьому відсутність повторень. Отримана послідовність $(x_{1},\cdots ,x_{n})$ інтерпретується як перестановка

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

Прямий метод генерування вимагає повторення вибору випадкового числа, якщо число, що випало, вже є в послідовності. Цього можна уникнути, якщо на $i$-му кроці (коли $x_{1},\cdots ,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. Типовий приклад такого тесту полягає у виборі деякої статистики, для якої розподіл відомий, і перевірці, чи дійсно розподіл цієї статистики на множині отриманих перестановок достатньо близький до цього розподілу.

Див. також

• Константа Голомба — Дікмана
• Перестановка
• Псевдовипадкова перестановка

Література

• Jim Pitman. Probability. — Springer Science & Business Media, 2012. — P. 153–. — ISBN 978-1-4612-4374-8.
• В. Г. Потемкин «Справочник по MATLAB» Работа с разреженными матрицами. - описано використання процедури randperm генерування випадкових перестановок у пакунку MATLAB.
• Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 2003. — С. 129-130. — ISBN 0-201-00023-7 / 5-8459-0122-7.
• Альфред В Ахо, Джон Э Хопкрофт, Джеффри Д Ульман. Алгоритмы. Построение и анализ. — Санкт-Петербург, Москва, Киев : Издательский дом "Вильямс", 2007. — С. 152-153 Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
• Арнольд В.И. Экспериментальное наблюдение математических фактов. — М. : МЦНМО, 2006. — С. 66-84. — (Летняя школа «Современная математика») — ISBN 978-5-94057-282-4.
• Т. Кристиансен,Н. Торкингтон. Perl. Библиотека программиста. — Питер, 2001. — С. У розділі 4 "Масиви" розглянуто все, що стосується операцій зі списками та масивами, зокрема пошук унікальних елементів, ефективне сортування та випадкові перестановки елементів. — ISBN 5-8046-0094-X.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. Алгоритмы: построение и анализ. — М. : "Вильямс", 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
• Random permutation generation — детальний виклад алгоритму тасування Кнута та його варіантів для генерування $k$-перестановок (перестановок $k$ елементів, вибраних зі списку) та $k$-підмножин
• Герасимов В. А. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру. RSDN Magazine #3-2010 (рос.)