Тасування Фішера — Єйтса — це алгоритм для тасування скінченної послідовності. Алгоритм бере список усіх елементів послідовності та послідовно визначає наступний елемент у перемішаній послідовності, випадковим чином вибираючи елемент зі списку, поки не залишиться жодного елемента. Алгоритм продукує незміщене пересташування: кожна перестановка є рівноймовірною. Сучасна версія алгоритму витрачає час, пропорційний кількості елементів, що тасуються, і перемішує їх на місці.
Тасування Фішера — Єйтса названо на честь Рональда Фішера та Френка Єйтса, які вперше його описали. Воно також відоме як тасування Кнута на честь Дональда Кнута. Варіант тасування Фішера — Єйтса, відомий як алгоритм Саттоло, може використовуватися для генерації випадкових циклічних перестановок довжини n замість випадкових перестановок.
Оригінальний метод Фішера та Єйтса
Оригінальне тасування Фішера — Єйтса було опубліковане в 1938 році Рональдом Фішером та Френком Єйтсом у їхній книзі «Статистичні таблиці для біологічних, сільськогосподарських та медичних досліджень». Примітка: 6-е видання, , доступне в мережі, але наводить інший алгоритм тасування від К. Р. Рао. Їхній опис алгоритму використовував олівець та папір; таблиця випадкових чисел забезпечувала випадковість. Основний метод генерації випадкової перестановки чисел від 1 до N виглядає так:
Запишіть числа від 1 до N. Виберіть випадкове число k між одиницею та кількістю незакреслених чисел, що залишилися (включно). Відраховуючи з нижнього кінця, викресліть k-те число, яке ще не викреслене, і запишіть його в кінці окремого списку. Повторюйте з кроку 2, поки всі числа не будуть викреслені. Послідовність чисел, записаних на кроці 3, тепер є випадковою перестановкою оригінальних чисел.
За умови, що випадкові числа, обрані на кроці 2 вище, є справді випадковими та незміщеними, такою ж буде і результуюча перестановка. Фішер та Єйтс подбали про те, щоб описати, як отримувати такі випадкові числа в будь-якому потрібному діапазоні з наданих таблиць способом, який уникає будь-якого зсуву. Вони також запропонували можливість використання простішого методу — вибір випадкових чисел від 1 до N і відкидання будь-яких дублікатів — для генерації першої половини перестановки, і застосування більш складного алгоритму лише до решти половини, де вибір дубліката числа в іншому випадку став би надзвичайно поширеним.
Сучасний алгоритм Сучасна версія тасування Фішера — Єйтса, розроблена для використання в комп'ютерах, була представлена Річардом Дурстенфельдом у 1964 році та популяризована Дональдом Е. Кнутом у «Мистецтво програмування» як «Алгоритм P (Тасування)». Жодна з статей Дурстенфельда, ні перше видання «Мистецтва програмування» Кнута не визнавали праці Фішера та Єйтса. Наступні видання «Мистецтва програмування» Кнута згадують внесок Фішера та Єйтса.
Алгоритм, описаний Дурстенфельдом, є більш ефективним, ніж наведений Фішером та Єйтсом: тоді як наївна комп'ютерна реалізація методу Фішера та Єйтса витрачала б марний час на підрахунок чисел, що залишилися, на кроці 3 вище, рішення Дурстенфельда полягає в переміщенні «вибраних» чисел у кінець списку шляхом обміну їх з останнім невибраним числом на кожній ітерації. Це зменшує часову складність алгоритму до порівняно з для наївної реалізації. Ця зміна дає наступний алгоритм (для масиву з нульовим індексуванням).
-- Щоб перемішати масив a з n елементів (індекси 0..n − 1): for i from n − 1 down to 1 do j ← випадкове ціле таке, що 0 ≤ j ≤ i обміняти a[j] і a[i]
Еквівалентна версія, яка перемішує масив у зворотному напрямку (від найменшого індексу до найбільшого): for i from 0 to n − 2 do j ← випадкове ціле таке, що i ≤ j ≤ n − 1 обміняти a[i] і a[j]
Оскільки обернена до рівномірно випадкової перестановки є рівномірно випадковою, можна так само виконувати цикли вище в іншому напрямку: for i from 1 to n − 1 do j ← випадкове ціле таке, що 0 ≤ j ≤ i обміняти a[j] і a[i]
Або: for i from n − 2 down to 0 do j ← випадкове ціле таке, що i ≤ j ≤ n − 1 обміняти a[i] і a[j]
Приклади
Метод олівця та паперу
Цей приклад переставляє літери від A до H, використовуючи оригінальний метод Фішера та Єйтса, починаючи з літер в алфавітному порядку:
Діапазон Жереб Початковий список Результат A B C D E F G H
Вибирається випадкове число j від 1 до 8. Якщо j=3, наприклад, тоді викреслюють третю літеру в початковому списку та записують її як результат:
Діапазон Жереб Початковий список Результат 1–8 3 A B D E F G H C
Обирається друге випадкове число, цього разу від 1 до 7. Якщо число 4, тоді викреслюють четверту літеру, яка ще не викреслена з початкового списку, та додають її до результату:
Діапазон Жереб Початковий список Результат 1–7 4 A B D F G H C E
Наступне випадкове число вибирається від 1 до 6, потім від 1 до 5, і так далі, завжди повторюючи процес викреслення, як описано вище:
Діапазон Жереб Початковий список Результат 1–6 5 A B D F H C E G 1–5 3 A B F H C E G D 1–4 4 A B F C E G D H 1–3 1 B F C E G D H A 1–2 2 B C E G D H A F C E G D H A F B
Сучасний метод
У версії алгоритму Дурстенфельда замість викреслення обраних літер та копіювання їх в інше місце, вони обмінюються з останньою ще не обраною літерою. Починаючи з літер від A до H, як і раніше:
Діапазон Жереб Початковий список Результат A B C D E F G H
Виберіть випадкове число j від 1 до 8, а потім поміняйте місцями j-ту та 8-му літери. Отже, якщо випадкове число дорівнює 6, наприклад, поміняйте місцями 6-ту та 8-му літери в списку:
Діапазон Жереб Початковий список Результат 1–8 6 A B C D E H G F
Наступне випадкове число вибирається від 1 до 7, і обрана літера міняється місцями з 7-ю літерою. Якщо це 2, наприклад, поміняйте місцями 2-гу та 7-му літери:
Діапазон Жереб Початковий список Результат 1–7 2 A G C D E H B F
Процес повторюється, поки перестановка не буде завершена:
Діапазон Жереб Початковий список Результат 1–6 6 A G C D E H B F 1–5 1 E G C D A H B F 1–4 3 E G D C A H B F 1–3 3 E G D C A H B F 1–2 1 G E D C A H B F
Після восьми кроків алгоритм завершено, і отримана перестановка — G E D C A H B F.
Реалізація на Python Цей приклад показує просту реалізацію тасування Фішера — Єйтса на Python. import random
def shuffle(numbers: list[int]) -> list[int]: for i in range(len(numbers) - 1, 0, -1): j = random.randint(0, i) numbers[i], numbers[j] = numbers[j], numbers[i] return numbers
Реалізація на JavaScript Цей приклад показує просту реалізацію тасування Фішера — Єйтса на JavaScript. function shuffleArray(array) { for (let i = array.length - 1; i >= 1; i--) { const j = Math.floor(Math.random() * (i + 1)); [array[i], array[j]] = [array[j], array[i]];
return array; }
Варіанти
Алгоритм Саттоло + Шість (3!) циклічних перестановок ABCD, згенерованих алгоритмом Саттоло Циклічнаперестановка Приклад BCDA ABCD→DABC→CDAB→BCDA→ABCD... DABC ABCD→BCDA→CDAB→DABC→ABCD... BDAC ABCD→CADB→DCBA→BDAC→ABCD... CADB ABCD→BDAC→DCBA→CADB→ABCD... CDBA ABCD→DCAB→BADC→CDBA→ABCD... DCAB ABCD→CDBA→BADC→DCAB→ABCD...
Дуже схожий алгоритм був опублікований у 1986 році Сандрою Саттоло для генерації рівномірно розподілених циклів (максимальної) довжини n. Єдина відмінність між алгоритмами Дурстенфельда та Саттоло полягає в тому, що в останньому, на кроці 2 вище, випадкове число j вибирається з діапазону між 1 та i−1 (а не між 1 та i) включно. Ця проста зміна модифікує алгоритм так, що результуюча перестановка завжди складається з єдиного циклу.
Фактично, як описано нижче, досить легко випадково реалізувати алгоритм Саттоло, коли мається намір використовувати звичайне тасування Фішера — Єйтса. Це призведе до зсуву результатів, оскільки перестановки будуть обиратися з меншого набору (n−1)! циклів довжини n, замість повного набору всіх n! можливих перестановок.
Те, що алгоритм Саттоло завжди продукує цикл довжини n, можна показати за допомогою математичної індукції. Припустімо за індукцією, що після початкової ітерації циклу решту ітерацій переставляють перші n − 1 елементів відповідно до циклу довжини n − 1 (ці ітерації, що залишилися, є просто алгоритмом Саттоло, застосованим до цих перших n − 1 елементів). Це означає, що якщо простежити за початковим елементом до його нової позиції p, потім за елементом, що спочатку знаходився в позиції p, до його нової позиції, і так далі, то повернутися до початкової позиції можна лише після відвідування всіх інших позицій. Припустімо, що початкова ітерація поміняла місцями кінцевий елемент з елементом у (не кінцевій) позиції k, і що наступна перестановка перших n − 1 елементів потім перемістила його до позиції l; ми порівнюємо перестановку π всіх n елементів з тією рештою перестановки σ перших n − 1 елементів. Простежуючи послідовні позиції, як щойно згадувалося, немає різниці між π та σ, доки не прийдемо до позиції k. Але тоді, згідно з π, елемент, що спочатку знаходився у позиції k, переміщується до кінцевої позиції, а не до позиції l, а елемент, що спочатку знаходився в кінцевій позиції, переміщується до позиції l. Звідти послідовність позицій для π знову слідує за послідовністю для σ, і всі позиції будуть відвідані, перш ніж повернутися до початкової позиції, як і вимагається.
Що стосується рівноймовірності перестановок, достатньо помітити, що модифікований алгоритм включає (n−1)! різних можливих послідовностей випадкових чисел, кожна з яких явно продукує різну перестановку, і кожна з яких зустрічається — за умови, що джерело випадкових чисел є незміщеним — з рівною ймовірністю. (n−1)! різних перестановок, що так продукуються, точно вичерпують набір циклів довжини n: кожен такий цикл має унікальний циклічний запис зі значенням n у кінцевій позиції, що дозволяє (n−1)! перестановкам решти значень заповнити інші позиції циклічного запису.
Приклад реалізації алгоритму Саттоло на Python:
from random import randrange
def sattolo_cycle(items) -> None: """Алгоритм Саттоло.""" i = len(items) while i > 1: i = i - 1 j = randrange(i) # 0 <= j <= i-1 items[j], items[i] = items[i], items[j]
Паралельні варіанти Було розроблено кілька паралельних алгоритмів тасування, заснованих на Фішері — Єйтсі.
У 1990 році Андерсон розробив паралельну версію для машин з невеликою кількістю процесорів, що мають доступ до спільної пам'яті. Алгоритм генерує випадкові перестановки рівномірно, за умови, що апаратне забезпечення працює справедливим чином.
У 2015 році Бачер та ін. створили MERGESHUFFLE, алгоритм, який ділить масив на блоки приблизно рівного розміру, використовує Фішера — Єйтса для тасування кожного блоку, а потім використовує випадкове злиття рекурсивно, щоб отримати перемішаний масив.
Порівняння з іншими алгоритмами тасування
Асимптотична часова та просторова складність тасування Фішера — Єйтса є оптимальною. У поєднанні з якісним незміщеним джерелом випадкових чисел воно також гарантовано дає незміщені результати. Порівняно з деякими іншими рішеннями, воно також має ту перевагу, що якщо потрібна лише частина результуючої перестановки, його можна зупинити на півшляху, або навіть зупиняти та перезапускати повторно, генеруючи перестановку поступово за потребою.
Наївний метод Наївний метод обміну кожного елемента з іншим елементом, вибраним випадковим чином з усіх елементів, є зміщеним. Різні перестановки матимуть різні ймовірності генерації, для кожного , оскільки кількість різних перестановок, , не ділить рівномірно кількість випадкових результатів алгоритму, . Зокрема, згідно з постулатом Бертрана існуватиме принаймні одне просте число між та , і це число ділитиме , але не ділитиме .
from random import randrange
def naive_shuffle(items) -> None: """Наївний метод. Це приклад того, чого не робити -- використовуйте замість нього Фішера–Єйтса.""" n = len(items) for i in range(n): j = randrange(n) # 0 <= j <= n-1 items[j], items[i] = items[i], items[j]
Сортування