Войти
A случайная перестановка - это случайное упорядочение набора объектов, то есть перестановка -значная случайная величина. Использование случайных перестановок часто является фундаментальным для областей, в которых используются рандомизированные алгоритмы, такие как теория кодирования, криптография и моделирование. Хорошим примером случайной перестановки является перетасовка колоды карт : в идеале это случайная перестановка 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 !, что дает равномерное распределение по всем таким перестановкам.
униформа без знака (m без знака); / * Возвращает случайное целое число 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. Первые n моментов этого распределения в точности соответствуют распределению Пуассона.
Как и в случае со всеми случайными процессами, качество результирующего распределения реализации рандомизированного алгоритма, такого как перемешивание Кнута (т. Е. Насколько оно близко к желаемому равномерному распределению) зависит от качества основного источника случайности, такого как генератор псевдослучайных чисел. Существует множество возможных тестов на случайность для случайных перестановок, таких как некоторые из тестов Дихарда. Типичный пример такого теста - взять некоторые из них, распределение которых известно, и проверить, насколько близко распределение этой статистики по набору случайно сгенерированных перестановок приближается к истинному распределению.
