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

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

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

Пошаговый метод перебора

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

{\begin{pmatrix}1&2&3&\cdots &n\\x_{1}&x_{2}&x_{3}&\cdots &x_{n}\\\end{pmatrix}},

показано здесь в двухстрочном обозначении .

Этот метод грубой силы потребует периодических повторных попыток всякий раз, когда выбранное случайное число является повторением уже выбранного числа. Этого можно избежать, если на i -м шаге (когда x ₁ , ..., 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 uniform(unsigned m); /* Returns a random integer 0 <= uniform(m) <= m-1 with uniform distribution */

void initialize_and_permute(unsigned permutation[], unsigned n)
{
    unsigned i;
    for (i = 0; i <= n-2; i++) {
        unsigned j = i+uniform(n-i); /* A random integer such that i ≤ j < n */
        swap(permutation[i], permutation[j]);   /* Swap the randomly picked element with permutation[i] */
    }
}

Обратите внимание, что если uniform() функция реализована просто как random() % (m) то в результатах появляется смещение, если количество возвращаемых значений random() не кратно m, но это становится незначительным, если количество возвращаемых значений random() на порядки превышает m.

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

Фиксированные точки

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

Тестирование на случайность

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

См. также

Формула выборки Юэнса — связь с популяционной генетикой
Фаро перетасовать
Константа Голомба – Дикмана
Статистика случайных перестановок
Алгоритмы перетасовки — метод случайной сортировки, метод итерационного обмена.
Псевдослучайная перестановка

Ссылки

^ Дюрстенфельд, Ричард (1 июля 1964 г.). «Алгоритм 235: Случайная перестановка» . Коммуникации АКМ . 7 (7): 420. дои : 10.1145/364520.364540 .

Внешние ссылки

Случайная перестановка в MathWorld
Генерация случайных перестановок - подробное и практическое объяснение алгоритма перетасовки Кнута и его вариантов для генерации k -перестановок (перестановок k элементов, выбранных из списка) и k -подмножеств (генерации подмножества элементов в списке без замены) с помощью псевдокода.

[1] Дюрстенфельд, Ричард (1 июля 1964 г.). «Алгоритм 235: Случайная перестановка» . Коммуникации АКМ . 7 (7): 420. дои : 10.1145/364520.364540 .

[1]