1. Прямий метод (елемент за елементом) [ правити | правити код ]
2. Тасування Кнута [ правити | правити код ]
3. Статистика на випадкових перестановках [ правити | правити код ]

open wikipedia design.

Випадкова перестановка - це випадкове впорядкування безлічі об'єктів, тобто випадкова величина , Елементарними подіями якої є перестановки . Використання випадкових перестановок часто є базою в областях, що використовують рандомізовані алгоритми . До таких областей відносяться теорія кодування , криптографія і моделювання . Хорошим прикладом випадкової перестановки є тасування колоди карт .

Прямий метод (елемент за елементом) [ правити | правити код ]

Одним з методів генерації випадкової перестановки множини з n елементів є використання рівномірного розподілу , Для чого вибираються послідовно випадкові числа між 1 і n, забезпечуючи при цьому відсутність повторень. Отримана послідовність (x 1, ..., x n) інтерпретується як перестановка

(1 2 3 ⋯ nx 1 x 2 x 3 ⋯ xn), {\ displaystyle {\ begin {pmatrix} 1 & 2 & 3 & \ cdots & n \\ x_ {1} & x_ {2} & x_ {3} & \ cdots & x_ {n} \ \\ end {pmatrix}},}

Прямий метод генерації вимагає повторення вибору випадкового числа, якщо випало число вже є в послідовності. Цього можна уникнути, якщо на i-му кроці (коли x 1, ..., x i - 1 вже обрані), вибирати випадкове число j між 1 і n - i + 1 і, потім, вибирати x i, рівним j -му невиділеного числу.

Тасування Кнута [ правити | правити код ]

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

Статистика на випадкових перестановках [ правити | правити код ]

Нерухомі точки [ правити | правити код ]

розподіл ймовірностей числа нерухомих точок в рівномірно розподілених випадкових перестановках на n елементах наближається до закону Пуассона при зростанні n. Підрахунок числа нерухомих точок є класичним прикладом використання формули включень-виключень , Яка показує, що ймовірність відсутності нерухомих точок наближається до 1 / e. При цьому математичне очікування числа нерухомих точок дорівнює 1 при будь-якому розмірі перестановки. [1]

Як і у всіх інших випадкових процесах, якість алгоритму генерації перестановок, зокрема, алгоритму тасування Кнута, залежить від покладеного в основу генератора випадкових чисел, такого як генератор псевдовипадкових чисел . Є велика кількість можливих тестів випадковості , Наприклад, тести diehard . Типовий приклад такого тесту полягає у виборі деякої статистики, для якої розподіл відомо, і перевірити, чи дійсно розподіл цієї статистики на безлічі отриманих перестановок досить близько до цього розподілу.

1. ↑ Д. Кнут, Р. Грехем, О. Паташнік. Конкретна математика. - Світ, 1998..

• Jim Pitman. Probability. - Springer Science & Business Media, 2012. - P. 153-. - ISBN 978-1-4612-4374-8 .
• В. Г. Потьомкін «Довідник по MATLAB» Робота з розрідженими матрицями. Описано використання процедури randperm генерації випадкових перестановок в пакеті MathLab.
• Альфред В. Ахо, Джон Хопкрофта, Джеффрі Д. Ульман. Структури даних і алгоритми. - Видавничий дім "Вільямс", 2003. - С. 129-130. - ISBN 0-201-00023-7 / 5-8459-0122-7.
• Альфред В Ахо, Джон Е Хопкрофта, Джеффрі Д Ульман. Алгоритми. Побудова і аналіз. - Санкт-Петербург, Москва, Київ: Видавничий дім "Вільямс", 2007. - С. 152-153 Глава 5. Імовірнісний аналіз і рандомізовані алгоритми.
• Арнольд В.І. Експериментальне спостереження математичних фактів. - М.: МЦНМО, 2006. - С. 66-84. - (Літня школа «Сучасна математика»). - ISBN 978-5-94057-282-4 .
• Т. Крістіансен, Н. Торкінгтон. Perl. Бібліотека програміста. - Пітер, 2001. - С. В розділі 4 "Масиви" розглядається все, що відноситься до операцій зі списками і масивами, в тому числі пошук унікальних елементів, ефективна сортування і випадкові перестановки елементів .. - ISBN 5-8046-0094-X .
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн K. Алгоритми: побудова й аналіз. - М.: "Вільямc", 2005. - С. Глава 5.3 рандомізовані алгоритми. - ISBN 5-8459-0857-4 .
• Борис Миколайович Іванов. Дискретна математика. Алгоритми і програми. Розширений курс. - М.: Известия, 2011. - С. 180, Випадкові перестановки. - ISBN 978-5-206-00824-1 .
• І.В. Красиков, І.Є. Красиков. Алгоритми. Просто як двічі два. - М.: Ексмо, 2007. - ISBN 978-5-699-21047-3 .
• Б.М. Іванов. Дискретна математика. Алгоритми і програми: Учеб. посібник. Просто як двічі два. - М.: Лабораторія Базових Знань, 2003. - С. 89. 4.8 Генерація випадкових перестановок. - (Технічний університет). - ISBN 5-93208-093-0 .

• Random permutation на MathWorld
• Random permutation generation - детальний виклад алгоритму тасування Кнута і його варіантів для генерації перестановок k -перестановок (перестановок k елементів, вибраних зі списку) і k -подмножеств
• Герасимов Василь Олександрович. Генерація випадкових поєднань. Генерація поєднання по його порядковому номеру. RSDN Magazine # 3-2010