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

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

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

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

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

<math>\begin{pmatrix}

1 & 2 & 3 & \cdots & n \\ x_1 & x_2 & x_3 & \cdots & x_n \\ \end{pmatrix},</math>

Прямой метод генерации требует повторения выбора случайного числа, если выпавшее число уже есть в последовательности. Этого можно избежать, если на i-ом шаге (когда x₁, …, x_{i − 1} уже выбраны), выбирать случайное число j между 1 и n − i + 1 и, затем, выбирать x_i, равным j-ому невыбранному числу.

Тасование Кнута

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

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

Неподвижные точки

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

Проверка случайности

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

См. также

• Постоянная Голомба — Дикмана
• Алгоритмы тасования — метод случайной сортировки, метод итеративных перестановок
• Случайная перестановка
• Криптоанализ LEX

Литература

• Jim Pitman. Probability. — Springer Science & Business Media, 2012. — P. 153–. — ISBN 978-1-4612-4374-8.
• В. Г. Потемкин «Справочник по MATLAB» Работа с разреженными матрицами. Описано использование процедуры randperm генерации случайных перестановок в пакете MathLab.
• Альфред В. Ахо, Джон Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. — Издательский дом "Вильямс", 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. Алгоритмы: построение и анализ. — М.: "Вильямc", 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.wolfram.com/RandomPermutation.html Random permutation] на MathWorld
• [www.techuser.net/randpermgen.html Random permutation generation] — детальное изложение алгоритма тасования Кнута и его вариантов для генерации перестановок k-перестановок (перестановок k элементов, выбранных из списка) и k-подмножеств
• Герасимов Василий Александрович. Генерация случайных сочетаний. Генерация сочетания по его порядковому номеру. [www.rsdn.ru/article/alg/Combine.xml RSDN Magazine #3-2010]

Отрывок, характеризующий Случайные перестановки

31 го декабря, накануне нового 1810 года, le reveillon [ночной ужин], был бал у Екатерининского вельможи. На бале должен был быть дипломатический корпус и государь.
На Английской набережной светился бесчисленными огнями иллюминации известный дом вельможи. У освещенного подъезда с красным сукном стояла полиция, и не одни жандармы, но полицеймейстер на подъезде и десятки офицеров полиции. Экипажи отъезжали, и всё подъезжали новые с красными лакеями и с лакеями в перьях на шляпах. Из карет выходили мужчины в мундирах, звездах и лентах; дамы в атласе и горностаях осторожно сходили по шумно откладываемым подножкам, и торопливо и беззвучно проходили по сукну подъезда.
Почти всякий раз, как подъезжал новый экипаж, в толпе пробегал шопот и снимались шапки.
– Государь?… Нет, министр… принц… посланник… Разве не видишь перья?… – говорилось из толпы. Один из толпы, одетый лучше других, казалось, знал всех, и называл по имени знатнейших вельмож того времени.
Уже одна треть гостей приехала на этот бал, а у Ростовых, долженствующих быть на этом бале, еще шли торопливые приготовления одевания.
Много было толков и приготовлений для этого бала в семействе Ростовых, много страхов, что приглашение не будет получено, платье не будет готово, и не устроится всё так, как было нужно.
Вместе с Ростовыми ехала на бал Марья Игнатьевна Перонская, приятельница и родственница графини, худая и желтая фрейлина старого двора, руководящая провинциальных Ростовых в высшем петербургском свете.
В 10 часов вечера Ростовы должны были заехать за фрейлиной к Таврическому саду; а между тем было уже без пяти минут десять, а еще барышни не были одеты.
Наташа ехала на первый большой бал в своей жизни. Она в этот день встала в 8 часов утра и целый день находилась в лихорадочной тревоге и деятельности. Все силы ее, с самого утра, были устремлены на то, чтобы они все: она, мама, Соня были одеты как нельзя лучше. Соня и графиня поручились вполне ей. На графине должно было быть масака бархатное платье, на них двух белые дымковые платья на розовых, шелковых чехлах с розанами в корсаже. Волоса должны были быть причесаны a la grecque [по гречески].
Все существенное уже было сделано: ноги, руки, шея, уши были уже особенно тщательно, по бальному, вымыты, надушены и напудрены; обуты уже были шелковые, ажурные чулки и белые атласные башмаки с бантиками; прически были почти окончены. Соня кончала одеваться, графиня тоже; но Наташа, хлопотавшая за всех, отстала. Она еще сидела перед зеркалом в накинутом на худенькие плечи пеньюаре. Соня, уже одетая, стояла посреди комнаты и, нажимая до боли маленьким пальцем, прикалывала последнюю визжавшую под булавкой ленту.
– Не так, не так, Соня, – сказала Наташа, поворачивая голову от прически и хватаясь руками за волоса, которые не поспела отпустить державшая их горничная. – Не так бант, поди сюда. – Соня присела. Наташа переколола ленту иначе.
– Позвольте, барышня, нельзя так, – говорила горничная, державшая волоса Наташи.
– Ах, Боже мой, ну после! Вот так, Соня.
– Скоро ли вы? – послышался голос графини, – уж десять сейчас.
– Сейчас, сейчас. – А вы готовы, мама?
– Только току приколоть.
– Не делайте без меня, – крикнула Наташа: – вы не сумеете!
– Да уж десять.
На бале решено было быть в половине одиннадцатого, a надо было еще Наташе одеться и заехать к Таврическому саду.
Окончив прическу, Наташа в коротенькой юбке, из под которой виднелись бальные башмачки, и в материнской кофточке, подбежала к Соне, осмотрела ее и потом побежала к матери. Поворачивая ей голову, она приколола току, и, едва успев поцеловать ее седые волосы, опять побежала к девушкам, подшивавшим ей юбку.
Дело стояло за Наташиной юбкой, которая была слишком длинна; ее подшивали две девушки, обкусывая торопливо нитки. Третья, с булавками в губах и зубах, бегала от графини к Соне; четвертая держала на высоко поднятой руке всё дымковое платье.
– Мавруша, скорее, голубушка!
– Дайте наперсток оттуда, барышня.
– Скоро ли, наконец? – сказал граф, входя из за двери. – Вот вам духи. Перонская уж заждалась.
– Готово, барышня, – говорила горничная, двумя пальцами поднимая подшитое дымковое платье и что то обдувая и потряхивая, высказывая этим жестом сознание воздушности и чистоты того, что она держала.
Наташа стала надевать платье.
– Сейчас, сейчас, не ходи, папа, – крикнула она отцу, отворившему дверь, еще из под дымки юбки, закрывавшей всё ее лицо. Соня захлопнула дверь. Через минуту графа впустили. Он был в синем фраке, чулках и башмаках, надушенный и припомаженный.
– Ах, папа, ты как хорош, прелесть! – сказала Наташа, стоя посреди комнаты и расправляя складки дымки.
– Позвольте, барышня, позвольте, – говорила девушка, стоя на коленях, обдергивая платье и с одной стороны рта на другую переворачивая языком булавки.
– Воля твоя! – с отчаянием в голосе вскрикнула Соня, оглядев платье Наташи, – воля твоя, опять длинно!
Наташа отошла подальше, чтоб осмотреться в трюмо. Платье было длинно.
– Ей Богу, сударыня, ничего не длинно, – сказала Мавруша, ползавшая по полу за барышней.
– Ну длинно, так заметаем, в одну минутую заметаем, – сказала решительная Дуняша, из платочка на груди вынимая иголку и опять на полу принимаясь за работу.
В это время застенчиво, тихими шагами, вошла графиня в своей токе и бархатном платье.
– Уу! моя красавица! – закричал граф, – лучше вас всех!… – Он хотел обнять ее, но она краснея отстранилась, чтоб не измяться.
– Мама, больше на бок току, – проговорила Наташа. – Я переколю, и бросилась вперед, а девушки, подшивавшие, не успевшие за ней броситься, оторвали кусочек дымки.
– Боже мой! Что ж это такое? Я ей Богу не виновата…
– Ничего, заметаю, не видно будет, – говорила Дуняша.
– Красавица, краля то моя! – сказала из за двери вошедшая няня. – А Сонюшка то, ну красавицы!…
В четверть одиннадцатого наконец сели в кареты и поехали. Но еще нужно было заехать к Таврическому саду.
Перонская была уже готова. Несмотря на ее старость и некрасивость, у нее происходило точно то же, что у Ростовых, хотя не с такой торопливостью (для нее это было дело привычное), но также было надушено, вымыто, напудрено старое, некрасивое тело, также старательно промыто за ушами, и даже, и так же, как у Ростовых, старая горничная восторженно любовалась нарядом своей госпожи, когда она в желтом платье с шифром вышла в гостиную. Перонская похвалила туалеты Ростовых.