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

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

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

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

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

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

Прямий метод генерування вимагає повторення вибору випадкового числа, якщо число, що випало, вже є в послідовності. Цього можна уникнути, якщо на ${\displaystyle i}$-му кроці (коли ${\displaystyle x_{1},\cdots ,x_{i-1}}$ вже вибрано), вибирати випадкове число ${\displaystyle j}$ між 1 і ${\displaystyle n-i+1}$ і, потім, вибирати ${\displaystyle x_{i}}$ рівним ${\displaystyle j}$-му невибраному числу.

Тасування Кнута

Простий алгоритм генерування випадкових перестановок з ${\displaystyle n}$ елементів (із рівномірним розподілом) без повторів, відомий як , починається з довільної перестановки (наприклад, з тотожної — без переставляння елементів), і проходить з позиції 1 до позиції ${\displaystyle n-1}$, переставляючи елемент на позиції ${\displaystyle i}$ з випадково вибраним елементом на позиціях від ${\displaystyle i}$ до ${\displaystyle n}$ включно. Легко показати, що в такий спосіб ми отримаємо всі перестановки ${\displaystyle n}$ елементів зі ймовірністю рівно ${\displaystyle 1/n!}$.

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

Нерухомі точки

Розподіл імовірностей числа нерухомих точок у рівномірно розподілених випадкових перестановках на ${\displaystyle n}$ елементах, у разі зростання ${\displaystyle n}$ , наближається до закону Пуассона. Підрахунок числа нерухомих точок є класичним прикладом використання формули включень-виключень, яка показує, що ймовірність відсутності нерухомих точок наближається до ${\displaystyle 1/e}$. При цьому математичне сподівання числа нерухомих точок дорівнює 1 за будь-якого розміру перестановки.

Перевірка випадковості

Як і у всіх інших випадкових процесах, якість алгоритму генерування перестановок, зокрема алгоритму тасування Кнута, залежить від покладеного в основу генератора випадкових чисел, такого як генератор псевдовипадкових чисел. Є багато можливих , наприклад, тести diehard. Типовий приклад такого тесту полягає у виборі деякої статистики, для якої розподіл відомий, і перевірці, чи дійсно розподіл цієї статистики на множині отриманих перестановок достатньо близький до цього розподілу.

Див. також

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

Примітки

1. Д. Кнут, Р. Грэхем, О. Паташник. Конкретная математика. — Мир, 1998. — С. 431.

Література

• Jim Pitman. Probability. — Springer Science & Business Media, 2012. — P. 153–. — .
• В. Г. Потемкин «Справочник по MATLAB» Работа с разреженными матрицами. - описано використання процедури randperm генерування випадкових перестановок у пакунку MATLAB.
• Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 2003. — С. 129-130. — / 5-8459-0122-7.
• Альфред В Ахо, Джон Э Хопкрофт, Джеффри Д Ульман. Алгоритмы. Построение и анализ. — Санкт-Петербург, Москва, Киев : Издательский дом "Вильямс", 2007. — С. 152-153 Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
• Арнольд В.И. Экспериментальное наблюдение математических фактов. — М. : МЦНМО, 2006. — С. 66-84. — (Летняя школа «Современная математика») — .
• Т. Кристиансен,Н. Торкингтон. Perl. Библиотека программиста. — Питер, 2001. — С. У розділі 4 "Масиви" розглянуто все, що стосується операцій зі списками та масивами, зокрема пошук унікальних елементів, ефективне сортування та випадкові перестановки елементів. — .
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. Алгоритмы: построение и анализ. — М. : "Вильямс", 2005. — С. Глава 5.3 Рандомизированные алгоритмы. — .
• Борис Николаевич Иванов. Дискретная математика. Алгоритмы и программы. Расширенный курс. — М. : Известия, 2011. — С. 180, Случайные перестановки. — .
• И.В. Красиков, И.Е. Красиков. Алгоритмы. Просто как дважды два. — М. : Эксмо, 2007. — .
• Б.Н. Иванов. Дискретная математика. Алгоритмы и программы: Учеб. пособие. Просто как дважды два. — М. : Лаборатория Базовых Знаний, 2003. — С. 89. 4.8 Генерация случайных перестановок. — (Технический университет) — .

Посилання

• Випадкова перестановка на MathWorld
• Random permutation generation — детальний виклад алгоритму тасування Кнута та його варіантів для генерування ${\displaystyle k}$-перестановок (перестановок ${\displaystyle k}$ елементів, вибраних зі списку) та ${\displaystyle k}$-підмножин
• Герасимов В. А. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру. RSDN Magazine #3-2010 (рос.)