Тасовка Фишера–Йейтса
-
Тасовка Фишера–Йейтса
- Алгоритм для перетасовки конечной последовательности
- Производит несмещенную перестановку с равной вероятностью
- Современная версия требует времени, пропорционального количеству элементов
-
История и методы
- Описан Рональдом Фишером и Фрэнком Йейтсом в 1938 году
- Современная версия разработана Ричардом Дюрстенфельдом в 1964 году
- Алгоритм Саттоло генерирует циклические перестановки длины n
-
Оригинальный метод Фишера и Йейтса
- Использует карандаш и бумагу для генерации случайных чисел
- Вычеркивает числа и записывает их в конец списка
- Повторяет процесс до завершения
-
Современный алгоритм
- Переставляет числа в конец списка, меняя их местами с последним незачеркнутым числом
- Снижает временную сложность до O(n)
-
Примеры
- Метод работы с карандашом и бумагой
- Современный метод с заменой букв
- Реализация на Python
-
Варианты
- Алгоритм «вывернутый наизнанку» для инициализации и перетасовки массива
- Алгоритм Саттоло для генерации циклов длины n
-
Параллельные варианты
- Разработаны параллельные алгоритмы перетасовки на основе метода Фишера—Йейтса
-
Алгоритмы перетасовки
- В 1990 году Андерсон разработал параллельную версию алгоритма для машин с небольшим количеством процессоров.
- В 2015 году Бахер и соавт. создали MERGESHUFFLE, алгоритм, использующий метод Фишера—Йейтса для перетасовки блоков массива.
-
Сравнение алгоритмов
- Асимптотическая временная и пространственная сложность тасовки Фишера–Йейтса оптимальна.
- Наивный метод замены элементов случайным образом предвзят.
- Метод сортировки присваивает случайные числа элементам и сортирует их, но требует больше пространства и не всегда дает объективные результаты.
-
Потенциальные источники предвзятости
- Ошибки при реализации могут привести к предвзятости, например, выбор случайных чисел из неправильного диапазона.
- Смещение по модулю возникает при использовании генераторов случайных чисел с фиксированным диапазоном.
- Метод получения случайных чисел в требуемых диапазонах, описанный Лемиром, является беспристрастным и почти не требует дорогостоящих операций.
-
Ограничения плавающей запятой
- В любом заданном диапазоне существует конечное число возможных значений с плавающей запятой.
- При разделении диапазона на сегменты, в некоторых сегментах будет больше возможных значений.
- Погрешность не будет демонстрировать систематической тенденции к снижению.
-
Генераторы псевдослучайных чисел
- Тасовка Фишера-Йейтса с генератором псевдослучайных чисел (PRNG) может производить меньше перестановок, чем возможных состояний PRNG.
- Количество состояний PRNG должно превышать количество перестановок на несколько порядков.
- Встроенные генераторы часто имеют 32 бита внутреннего состояния, что ограничивает количество возможных перестановок.
-
Проблемы с линейными конгруэнтными PRNG
- Младшие разряды линейного конгруэнтного PRNG менее случайны, чем старшие.
- Взятие остатка от деления на степень двойки приводит к отбрасыванию старших разрядов.
- Некачественные RNG и PRNG приводят к некачественному перетасовыванию.
-
Свойства перестановок Фишера-Йейтса
- Перестановка Фишера-Йейтса не зависит от перетасовываемых элементов.
- Свойства перестановок стандартного набора S = {1, 2, …, n} были тщательно изучены.
-
Применение и рекомендации
- Перестановка Фишера-Йейтса используется в потоковом шифре RC4 и алгоритме R.
- Метод Фишера-Йейтса беспристрастен, в отличие от наивного метода.
- Алгоритм Саттоло является специализацией метода Фишера-Йейтса, где ни один элемент не остается в исходном положении.