Метод генерации случайной перестановки, алгоритм Фишера-Йетса — различия между версиями
Dantesto (обсуждение | вклад) |
Dantesto (обсуждение | вклад) (→Источники информации) |
||
Строка 40: | Строка 40: | ||
==Источники информации== | ==Источники информации== | ||
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2 | *Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2 | ||
− | *[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование | + | *[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия - Тасование Фишера-Йетса] |
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle] | *[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia - Fisher-Yates shuffle] | ||
Версия 00:13, 11 декабря 2016
Тасование Фишера-Йетса (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) — алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма
Содержание
Применение алгоритма
Задача:
Необходимо сгенерировать случайную перестановку из
чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
числа в заданном интервале.
Решение:
Пусть
Следующий алгоритм решает задачу:
int[n] randomPermutation(a: int[n]): // n — длина перестановки for i = n downto 1 j = random(1..i) swap(a[i], a[j]) return a
Обоснование
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть
способов выбрать элемент, способов выбрать элемент... способ выбрать последний элемент. Таким образом, последовательность длины мы можем получить способами, что совпадает с числом различных перестановок длины . Это означает, что вероятность выбрать любую перестановку длины равна , то есть все перестановки равновероятны.Неправильные способы реализации
Небольшая модификация этого алгоритма, может резко сказаться на его корректности.
Пример неправильной реализации:
for i = n downto 1 swap(i, random(1..n))
В данном случае число способов сгенерировать последовательность равно
, в то время как существует всего возможных перестановок из элементов. Поскольку никогда не может делиться на без остатка при (так как делится на число , которое не имеет с общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.Другой пример неправильной реализации:
for i = n downto 1 swap(random(1..n), random(1..n))
Теперь уже число способов сгенерировать последовательность равно
. По той же причине, что и раньше не делится на без остатка при ,следовательно некоторые перестановки будут появляться еще чаще.См.также
Источники информации
- Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2
- Википедия - Тасование Фишера-Йетса
- Wikipedia - Fisher-Yates shuffle