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]