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

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

24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

Антивоенный комитет России

Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
meduza.io, Популярная политика, Новая газета, zona.media, Майкл Наки.

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

Применение алгоритма

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

Решение:

Пусть

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

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

 int[n] randomPermutation(a: int[n]):   // 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(a[i], a[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] общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.

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

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

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

См.также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Метод_генерации_случайной_перестановки,_алгоритм_Фишера-Йетса&oldid=83383»