Метод генерации случайной перестановки, алгоритм Фишера-Йетса

Материал из Викиконспекты
Перейти к: навигация, поиск

Тасование Фишера-Йетса (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) — алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества. Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма O(n).

Содержание

[править] Применение алгоритма

Задача:
Необходимо сгенерировать случайную перестановку из n чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.

[править] Решение:

Пусть

  • \mathtt{random(1..i) } генерирует случайное число в отрезке [1;\; i]

Следующий алгоритм решает задачу:

 int[n] randomPermutation(a: int[n]):   // n — длина перестановки 
   for i = n downto 1
     j = random(1..i)
     swap(a[i], a[j])
   return a

[править] Обоснование

На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть n способов выбрать 1 элемент, n - 1 способов выбрать 2 элемент... 1 способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины n мы можем получить $$n \times (n - 1) \times \ldots \times 1 = n! $$ способами, что совпадает с числом различных перестановок длины n. Это означает, что вероятность выбрать любую перестановку длины n равна \dfrac{1}{n!}, то есть все перестановки равновероятны.

[править] Неправильные способы реализации

Небольшая модификация этого алгоритма, может резко сказаться на его корректности.

[править] Пример неправильной реализации:

 for i = n downto 1
   swap(a[i], a[random(1..n)])

В данном случае число способов сгенерировать последовательность равно n^n, в то время как существует всего n! возможных перестановок из n элементов. Поскольку n^n никогда не может делиться на n! без остатка при n > 2 (так как n! делится на число n - 1 , которое не имеет с n общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

[править] Другой пример неправильной реализации:

 for i = n downto 1
   swap(a[random(1..n)], a[random(1..n)])

Теперь уже число способов сгенерировать последовательность равно (n^2)^n. По той же причине, что и раньше (n^2)^n не делится на n! без остатка при n > 2, следовательно некоторые перестановки будут появляться еще чаще.

[править] См.также

[править] Источники информации

Личные инструменты
Пространства имён
Варианты
Действия
Навигация
Инструменты