Открыть сервис
Главная → Блог → Тасование Фишера-Йетса

Тасование Фишера-Йетса

Тасование Фишера-Йетса (также известное как алгоритм Кнута или тасование методом обратной итерации) — это алгоритм случайной перестановки элементов конечного множества, который генерирует равномерно распределённую случайную перестановку. Алгоритм гарантирует, что каждая возможная перестановка из n элементов имеет одинаковую вероятность (1/n!) быть полученной, при условии использования качественного генератора случайных чисел.

История

Алгоритм был впервые описан Рональдом Фишером и Фрэнком Йетсом в 1938 году в книге «Statistical Tables for Biological, Agricultural and Medical Research». Первоначальная версия представляла собой ручной метод, описанный в виде таблицы, где на каждом шаге случайным образом выбирался элемент из оставшихся и записывался в новый список. Этот процесс требовал физического удаления выбранных элементов из исходного набора, что делало его трудоёмким для больших массивов данных.

В 1964 году Ричард Дурстенфельд опубликовал модификацию, которая позволила выполнять тасование на месте, без использования дополнительной памяти. В 1969 году Дональд Кнут подробно описал этот алгоритм в первом томе своей книги «Искусство программирования», после чего он стал широко известен как «алгоритм Кнута». Современная версия, часто называемая «тасованием Фишера-Йетса», объединяет вклад всех трёх учёных.

Описание алгоритма

Классическая версия (Фишера-Йетса)

Исходная версия алгоритма работает следующим образом:

  1. Записывается список из n элементов (не обязательно различных).
  2. Пока в списке остаются элементы:
  • Выбирается случайный элемент из оставшихся.
  • Он удаляется из исходного списка и добавляется в конец нового списка.
  1. Новый список содержит все элементы в случайном порядке.

Недостатком этого метода является необходимость в дополнительной памяти для хранения нового списка, а также затраты времени на удаление элементов из середины списка (O(n) для каждого удаления в массиве).

Современная версия (Дурстенфельда)

Алгоритм Дурстенфельда выполняет тасование на месте, что экономит память и ускоряет выполнение:

  1. Для i от n-1 до 1 (включительно):
  • Выбирается случайное целое число j в диапазоне от 0 до i (включительно).
  • Элементы с индексами i и j меняются местами.

После завершения цикла массив оказывается случайно переставленным. Этот алгоритм имеет временную сложность O(n) и пространственную сложность O(1) (не считая входного массива).

Пример работы

Рассмотрим массив [A, B, C, D] (n=4):

  • i=3: j выбирается из {0,1,2,3}. Пусть j=1. Меняем местами A[3]=D и A[1]=B → [A, D, C, B].
  • i=2: j выбирается из {0,1,2}. Пусть j=0. Меняем местами A[2]=C и A[0]=A → [C, D, A, B].
  • i=1: j выбирается из {0,1}. Пусть j=0. Меняем местами A[1]=D и A[0]=C → [D, C, A, B].
  • i=0: цикл завершается.

Результат: [D, C, A, B].

Математическое обоснование

Алгоритм гарантирует равномерное распределение перестановок. Доказательство основано на том, что на каждом шаге i вероятность выбора любого из оставшихся элементов равна 1/(i+1). Общая вероятность получения конкретной перестановки вычисляется как произведение вероятностей на каждом шаге:

P(конкретная перестановка) = (1/n) × (1/(n-1)) × ... × (1/1) = 1/n!

Это соответствует равномерному распределению, так как всего существует n! возможных перестановок.

Реализация

Псевдокод

`` function fisher_yates_shuffle(array): n = length(array) for i from n-1 down to 1: j = random_integer(0, i) swap(array[i], array[j]) return array ``

Пример на Python

```python import random

def fisher_yates_shuffle(arr): n = len(arr) for i in range(n-1, 0, -1): j = random.randint(0, i) arr[i], arr[j] = arr[j], arr[i] return arr ```

Пример на C++

```cpp

include <algorithm>

include <random>

template<typename RandomAccessIterator, typename URNG> void fisher_yates_shuffle(RandomAccessIterator first, RandomAccessIterator last, URNG&& g) { for (auto i = last - first - 1; i > 0; --i) { std::uniform_int_distribution<decltype(i)> dist(0, i); auto j = dist(g); std::iter_swap(first + i, first + j); } } ```

Свойства и особенности

Равномерность

При использовании качественного генератора случайных чисел (например, криптостойкого ГСЧ) алгоритм даёт идеально равномерное распределение. Использование встроенного генератора rand() в некоторых языках может привести к смещению из-за ограниченного периода или нелинейности.

Обратимость

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

Неустойчивость

Тасование не сохраняет относительный порядок одинаковых элементов (если таковые имеются). Для устойчивого тасования (с сохранением порядка равных элементов) требуется другой подход.

Применение

Компьютерные науки

  • Перемешивание данных: подготовка наборов данных для машинного обучения (например, разделение на обучающую и тестовую выборки).
  • Алгоритмы рандомизации: основа для многих вероятностных алгоритмов, таких как быстрая сортировка с рандомизированным выбором опорного элемента.
  • Тестирование: генерация случайных тестовых данных для проверки корректности алгоритмов сортировки.

Игры и развлечения

  • Карточные игры: симуляция тасования колоды в компьютерных играх, онлайн-покере и казино.
  • Генерация уровней: случайное расположение элементов в играх-головоломках (например, «Сапёр»).
  • Лотереи: случайное распределение призов или номеров.

Криптография

  • Генерация ключей: создание случайных перестановок для шифров (например, в алгоритме RC4).
  • Криптоанализ: проверка стойкости шифров путём статистического анализа перестановок.

Научные исследования

  • Метод Монте-Карло: случайная перестановка данных для оценки статистических параметров.
  • Биоинформатика: перемешивание последовательностей ДНК для проверки гипотез о значимости совпадений.

Ошибки реализации

Неправильный диапазон случайных чисел

Наиболее распространённая ошибка — выбор j из диапазона от 0 до n-1 на каждом шаге, а не от 0 до i. Это приводит к неравномерному распределению, так как некоторые перестановки становятся более вероятными. Например, при n=3 такая ошибка даёт вероятность 2/9 для некоторых перестановок вместо 1/6.

Использование некачественного ГСЧ

Применение линейного конгруэнтного генератора (например, rand() в C) может привести к корреляции между последовательными случайными числами, что нарушает равномерность. Для криптографических приложений требуется использование криптостойких ГСЧ (например, std::random_device или secrets в Python).

Побочные эффекты

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

Сравнение с другими алгоритмами

Алгоритм Саттоло

Алгоритм, предложенный Сандрой Саттоло в 1986 году, также выполняет тасование на месте, но использует прямой проход (от 0 до n-1). Он эквивалентен алгоритму Фишера-Йетса, но менее интуитивен и реже используется.

Тасование методом «наивного» обмена

Наивный подход, при котором каждый элемент меняется местами со случайным элементом из всего массива, не даёт равномерного распределения. Например, при n=3 некоторые перестановки имеют вероятность 4/27, а другие — 5/27.

Алгоритм «колоды карт»

Имитация физического тасования колоды (например, методом «рифлёного» тасования) не является равномерным и требует многократного повторения для достижения приемлемой случайности.

Интересные факты

  • Алгоритм Фишера-Йетса используется в стандартной библиотеке C++ (std::shuffle), в Python (random.shuffle), в Java (Collections.shuffle) и многих других языках.
  • В 2012 году исследователи из Google обнаружили, что встроенный генератор случайных чисел в языке JavaScript (V8) имел недостаточную энтропию, что позволяло предсказывать результаты тасования в онлайн-играх.
  • Алгоритм может быть адаптирован для работы с бесконечными потоками данных (например, для случайной выборки из потока неизвестного размера — алгоритм резервуарной выборки).
  • При n=1 алгоритм не выполняет никаких операций, что корректно, так как единственная перестановка тривиальна.

Источники

  • Fisher, R. A.; Yates, F. (1938). Statistical Tables for Biological, Agricultural and Medical Research.
  • Knuth, D. E. (1969). The Art of Computer Programming, Volume 2: Seminumerical Algorithms.
  • Durstenfeld, R. (1964). «Algorithm 235: Random permutation». Communications of the ACM.
  • Cormen, T. H. et al. (2009). Introduction to Algorithms, 3rd edition.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →

Похожие материалы