Случайные перестановки

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Прямой метод (элемент за элементом)[править | править вики-текст]

Одним из методов генерации случайной перестановки множества из n элементов является использование равномерного распределения, для чего выбираются последовательно случайные числа между 1 и n, обеспечивая при этом отсутствие повторений. Полученная последовательность (x1, ..., xn) интерпретируется как перестановка

\begin{pmatrix}
1 & 2 & 3 & \cdots & n \\
x_1 & x_2 & x_3 & \cdots & x_n \\
\end{pmatrix},

Прямой метод генерации требует повторения выбора случайного числа, если выпавшее число уже есть в последовательности. Этого можно избежать, если на i-ом шаге (когда x1, ..., xi − 1 уже выбраны), выбирать случайное число j между 1 и ni + 1 и, затем, выбирать xi, равным j-ому невыбранному числу.

Тасование Кнута[править | править вики-текст]

Простой алгоритм генерации случайных перестановок из n элементов (с равномерным распределением) без повторов, известный как тасование Кнута, начинается с произвольной перестановки (например, с тождественной – без перестановки элементов), и проходит с позиции 1 до позиции n − 1, переставляя элемент на позиции i со случайно выбранным элементом на позициях от i до n включительно. Легко показать, что таким способом мы получим все перестановки n элементов с вероятность в точности 1/n!.

Статистика на случайных перестановках[править | править вики-текст]

Фиксированные точки[править | править вики-текст]

Распределение вероятностей числа неподвижных точек в равномерно распределенных случайных перестановках подчиняется закону Пуассона. Подсчет числа неподвижных точек является классическим примером использования формулы включений-исключений, которая показывает, что вероятность отсутствия неподвижных точек приближается к 1/e. При этом математическое ожидание числа неподвижных точек равно 1 при любом размере перестановки.[1]

Проверка случайности[править | править вики-текст]

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

Смотрите также[править | править вики-текст]

Внешние ссылки[править | править вики-текст]

  • Random permutation на MathWorld
  • Random permutation generation – детальное изложение алгоритма тасования Кнута и его вариантов для генерации перестановок k-перестановок (перестановок k элементов, выбранных из списка) и k-подмножеств
  • В.Г.Потемкин "Справочник по MATLAB" Работа с разреженными матрицами. Описано использование процедуры randperm генерации случайных перестановок в пакете MathLab.
  • Герасимов Василий Александрович. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру. RSDN Magazine #3-2010
  • Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман Структуры данных и алгоритмы. — Издательский дом "Вильямс".
  • Альфред В Ахо, Джон Э Хопкрофт, Джеффри Д Ульман Алгоритмы. Построение и анализ. — Санкт-Петербург, Москва, Киев: Издательский дом "Вильямс", 2007. — С. 152-153 Глава 5. Вероятностный анализ и рандомизированные алгоритмы.
  • Арнольд В.И Экспериментальное наблюдение математических фактов. — М.: МЦНМО, 2006. — С. 66-84; Лекция 3. Случайные перестановки и диаграммы Юнга их циклов. — (Летняя школа «Современная математика»).
  • Т. Кристиансен,Н. Торкингтон Perl. Библиотека программиста. — Питер, 2001. — С. В главе 4 "Массивы" рассматривается все, что относится к операциям со списками и массивами, в том числе поиск уникальных элементов, эффективная сортировка и случайные перестановки элементов..
  • Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. Алгоритмы: построение и анализ. — М.: "Вильямc", 2005. — С. Глава 5.3 Рандомизированные алгоритмы.
  • Борис Николаевич Иванов. Дискретная математика. Алгоритмы и программы. Расширенный курс. — М.: Известия, 2011. — С. 180, Случайные перестановки.
  • И.В. Красиков, И.Е. Красиков Алгоритмы. Просто как дважды два. — М.: Эксмо, 2007.
  • Б.Н. Иванов Дискретная математика. Алгоритмы и программы: Учеб. пособие. Просто как дважды два. — М.: Лаборатория Базовых Знаний, 2003. — С. 89. 4.8 Генерация случайных перестановок. — (Технический университет).


Примечания[править | править вики-текст]

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