21221

четверг, 16 июня 2016 г.

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

https://ru.wikipedia.org/wiki/Тасование_Фишера–Йетса

Тасование Фишера–Йетса (названо в честь Рональда Фишера и Франка Йетса (Frank Yates)), известное также под именем Тасование Кнута (в честь Дональда Кнута), — это алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайноготасования множества. Вариант тасования Фишера-Йетса, известный как алгоритм Саттоло (Sattolo), может быть использован для генерации случайного цикла перестановок длины n. Правильно реализованный алгоритм тасования Фишера-Йетса несмещённый, так что каждая перестановка генерируется с одинаковой вероятностью. Современная версия алгоритма очень эффективна и требует время, пропорциональное числу элементов множества, и не требует дополнительного пространства.
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат.
Современный вариант алгоритма тасования Фишера-Йетса, предназначенный для использования в компьютерах, был представлен Ричардом Дурштенфельдом (Richard Durstenfeld) в 1964-м году в журнале Communications of the ACM том 7, выпуск 7, под названием «Algorithm 235: Random permutation», и был популяризован Дональдом Кнутом во втором томе его книги Искусство программирования как «Алгоритм P». Ни Дуршенфельд, ни Кнут в первом издании книги не упомянули об алгоритме Фишера и Йетса, и, похоже, не были осведомлены о нём. Во втором издании книги Искусство программирования, однако, это упущение было исправлено
Алгоритм, описанный Дуршенфельдом, отличается от алгоритма Фишера и Йетса в небольших, но существенных деталях. Чтобы компьютерная реализация алгоритма не тратила бесполезно время на перебор оставшихся чисел на шаге 3, у Дуршенфельда на каждой итерации выбираемые числа переносились в конец списка путём перестановки с последним невыбранным числом. Эта модификация сокращала временную сложность алгоритма до O(n), по сравнению с O(n2) для исходного алгоритма. Это изменение приводит к следующему алгоритму.
Для тасования массива a из n элементов (индексы 0..n-1):
  для всех i от n − 1 до 1 выполнить
       j ← случайное число 0 ≤ j ≤ i
       обменять местами a[j] и a[i]

1 комментарий:

  1. Пусть
    random(1..i) генерирует случайное число в интервале [1; i]
    Следующий алгоритм решает задачу:
    int[] randomPermutation(int[] a) // n — длина перестановки
    for i = n downto 1
    j = random(1..i)
    swap(a[i], a[j])
    return a

    http://goo.gl/rKjAfg

    ОтветитьУдалить