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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Постановка задачи)
Строка 2: Строка 2:
 
Основная процедура тасования Фишера – Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
 
Основная процедура тасования Фишера – Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма <tex> O(n)</tex>
  
==Постановка задачи==
+
'''Задача:'''
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если есть в наличии функция для генерации случайного числа в заданном интервале.  
+
Необходимо сгенерировать случайную перестановку из <tex> n </tex> чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного
 +
числа в заданном интервале.
 +
 
 
==Решение==
 
==Решение==
 
Пусть <br/>
 
Пусть <br/>

Версия 04:27, 23 января 2016

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

Задача:

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

Решение

Пусть

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

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

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

Обоснование

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

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

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

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

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


См.также

Источники информации