Случайная перестановка — это случайное упорядочение набора объектов, то есть случайная величина со значением перестановки . Использование случайных перестановок распространено в азартных играх и в рандомизированных алгоритмах в теории кодирования , криптографии и моделировании . Хорошим примером случайной перестановки является честное тасование стандартной колоды карт : в идеале это случайная перестановка 52 карт.
Один из алгоритмов для генерации случайной перестановки множества размера n равномерно случайным образом , т. е. таким образом, чтобы каждая из n ! перестановок появлялась с равной вероятностью, заключается в генерации последовательности путем равномерного случайного выбора целого числа от 1 до n (включительно) последовательно и без замены n раз, а затем в интерпретации этой последовательности ( x 1 , ..., x n ) как перестановки
здесь показано в двухстрочной записи .
Неэффективный метод грубой силы для выборки без замены может выбирать из чисел от 1 до 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 uniform ( unsigned m ); /* Возвращает случайное целое число 0 <= uniform(m) <= m-1 с равномерным распределением */ void initialize_and_permute ( unsigned permutation [], unsigned n ) { unsigned i ; for ( i = 0 ; i <= n -2 ; i ++ ) { unsigned j = i + uniform ( n - i ); /* Случайное целое число, такое что i ≤ j < n */ swap ( permutation [ i ], permutation [ j ]); /* Поменять местами случайно выбранный элемент с permutation[i] */ } } Если uniform()функция реализована просто как random() % (m), то возникнет смещение в распределении перестановок, если число возвращаемых значений random()не кратно m. Однако этот эффект невелик, если число возвращаемых значений на random()порядки больше m.
Как и во всех вычислительных реализациях случайных процессов, качество распределения, генерируемого реализацией рандомизированного алгоритма, такого как тасовка Фишера-Йетса, т. е. насколько близко фактически сгенерированное распределение к желаемому распределению, будет зависеть от качества базовых источников случайности в реализации, таких как генераторы псевдослучайных чисел или аппаратные генераторы случайных чисел . Существует множество тестов случайности для случайных перестановок, таких как тест «перекрывающихся перестановок» тестов Diehard . Типичная форма таких тестов заключается в том, чтобы взять некоторую статистику перестановок , для которой распределение теоретически известно, а затем проверить, близко ли распределение этой статистики на наборе случайно сгенерированных перестановок из реализации к распределению этой статистики из истинного распределения.
Распределение вероятностей для числа неподвижных точек равномерно распределенной случайной перестановки из n элементов приближается к распределению Пуассона с ожидаемым значением 1 по мере роста n . [1] Первые n моментов этого распределения в точности соответствуют моменту распределения Пуассона. В частности, вероятность того, что случайная перестановка не имеет неподвижных точек (т. е. что перестановка является расстройством ) , приближается к 1/ e по мере роста n .