PROFILPELAJAR.COM

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

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

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

Одним з методів генерування випадкової перестановки множини з $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 за будь-якого розміру перестановки^[1].

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

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

Див. також

Примітки

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

Література

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 (рос.)