Случайная перестановка является случайным упорядочением множества объектов, то есть перестановка -значной случайной величины . Использование случайных перестановок часто является фундаментальным для областей, в которых используются рандомизированные алгоритмы, такие как теория кодирования , криптография и моделирование . Хорошим примером случайной перестановки является перетасовки из колоды карт : это в идеале случайная перестановка из 52 карт.
Генерация случайных перестановок
Метод перебора по входу
Один из методов генерации случайной перестановки набора длины n равномерно случайным образом (т. Е. Каждая из n ! Перестановок с равной вероятностью появится) состоит в генерации последовательности путем последовательного выбора случайного числа от 1 до n , гарантируя не является повторением, и интерпретируя эту последовательность ( x 1 , ..., x n ) как перестановку
показаны здесь в двухстрочных обозначениях .
Этот метод грубой силы потребует периодических повторных попыток всякий раз, когда выбранное случайное число является повторением уже выбранного числа. Этого можно избежать, если на i- м шаге (когда x 1 , ..., x i - 1 уже выбраны) выбрать случайным образом число j от 1 до n - i + 1 и установить x i равным к j- му наибольшему из невыбранных чисел.
Фишер-Йейтс тасует
Простой алгоритм для генерации перестановки из n элементов равномерно случайным образом без повторных попыток, известный как тасование Фишера – Йейтса , состоит в том, чтобы начать с любой перестановки (например, тождественной перестановки ), а затем пройти через позиции от 0 до n - 2. (мы используем соглашение, согласно которому первый элемент имеет индекс 0, а последний элемент имеет индекс n - 1), и для каждой позиции i меняем местами текущий там элемент со случайно выбранным элементом из позиций с i по n - 1 (конец) , включительно. Легко проверить, что любая перестановка n элементов будет произведена этим алгоритмом с вероятностью ровно 1 / n !, Таким образом давая равномерное распределение по всем таким перестановкам.
беззнаковая униформа ( unsigned m ); / * Возвращает случайное целое число 0 <= uniform (m) <= m-1 с равномерным распределением * /void initialize_and_permute ( беззнаковая перестановка [], беззнаковый n ) { беззнаковый i ; for ( i = 0 ; i <= n -2 ; i ++ ) { без знака j = i + uniform ( n - i ); / * Случайное целое число такое, что i ≤ j swap ( перестановка [ i ], перестановка [ j ]); / * Заменить случайно выбранный элемент перестановкой [i] * / } }
Обратите внимание, что если uniform()
функция реализована просто так, random() % (m)
то смещение результатов вводится, если количество возвращаемых значений random()
не кратно m, но это становится несущественным, если количество возвращаемых значений на random()
порядки больше, чем m.
Статистика случайных перестановок
Фиксированные точки
Распределение вероятностей количества фиксированных точек в равномерно распределенной случайной перестановке приближается к распределению Пуассона с ожидаемым значением 1 по мере роста n . В частности, это элегантное применение принципа включения-исключения, чтобы показать, что вероятность отсутствия неподвижных точек приближается к 1 / e . Когда п является достаточно большим, то распределение вероятностей из неподвижных точек почти распределение Пуассона с ожидаемым значением 1. [1] Первые п моменты этого распределения в точности те распределения Пуассона.
Проверка на случайность
Как и в случае со всеми случайными процессами, качество результирующего распределения реализации рандомизированного алгоритма, такого как перемешивание Кнута (то есть, насколько оно близко к желаемому равномерному распределению), зависит от качества базового источника случайности, такого как псевдослучайных чисел . Существует множество возможных тестов на случайность для случайных перестановок, например, некоторые из тестов Дихарда . Типичный пример такого теста - взять некоторую статистику перестановок, для которой известно распределение, и проверить, насколько близко распределение этой статистики на множестве случайно сгенерированных перестановок приближается к истинному распределению.
Смотрите также
- Формула выборки Ювенса - связь с популяционной генетикой
- Перетасовка фаро
- Константа Голомба – Дикмана
- Статистика случайных перестановок
- Алгоритмы перемешивания - метод случайной сортировки, метод итеративного обмена
Рекомендации
- ^ Дюрстенфельд, Ричард (1964-07-01). «Алгоритм 235: Случайная перестановка» . Коммуникации ACM . 7 (7): 420. DOI : 10,1145 / 364520,364540 .
Внешние ссылки
- Случайная перестановка в MathWorld
- Генерация случайной перестановки - подробное и практическое объяснение алгоритма тасования Кнута и его вариантов для генерации k -перестановок (перестановок k элементов, выбранных из списка) и k -подмножеств (генерации подмножества элементов в списке без замены) с псевдокодом