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

Пусть произвольно выбранная перестановка целых чисел например, тождественная. Случайную перестановку можно получить за линейное время из выбранной перестановки выполнив в ней транспозиций (см. п. 7.4).

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

Положим равной исходной перестановке Каждая следующая перестановка получается из предыдущей перестановки транспозицией элементов ил где Между элементами перестановок выполняются равенства где

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

Вероятности данных событий, согласно схеме формирования перестановок равны

Условие в событии, обеспечивает выбор элемента из множества которое совпадает с множеством Индекс же элемента является независимой случайной величиной с равномерным распределением на отрезке целых чисел.

Теперь заметим, что

Рассмотренный метод генерации случайной перестановки представлен в алгоритме 4.15.

Алгоритм 4.15. Генерация случайной перестановки

(см. скан)