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

Привет, Вы узнаете о том , что такое случайная перестановка, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое случайная перестановка , настоятельно рекомендую прочитать все из категории Дискретная математика. Теория множеств . Теория графов . Комбинаторика..

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

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

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

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

Простой алгоритм для генерации перестановки из n элементов равномерно случайным образом без повторных попыток, известный как перестановка Фишера-Йетса , заключается в том, чтобы начать с любой перестановки (например, тождественной перестановки ), а затем пройти по позициям от 0 до n − 2 (мы используем соглашение, где первый элемент имеет индекс 0, а последний элемент имеет индекс n − 1), и для каждой позиции i поменять текущий элемент на случайно выбранный элемент из позиций с i по n − 1 (конец) включительно. Об этом говорит сайт https://intellect.icu . Любая перестановка из 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.

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

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

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

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