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

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

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

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

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

$\left(\begin{array}{ccccc}1& 2& 3& \cdots & n\\ x_1& x_2& x_3& \cdots & x_n\end{array}\right),$

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

Див. також

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

Література

• Шаблон:Книга
• В. Г. Потемкин «Справочник по MATLAB» Работа с разреженными матрицами. - описано використання процедури randperm генерування випадкових перестановок у пакунку MATLAB.
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Посилання

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