Fisher-Yatesův algoritmus (pojmenovaný po Ronaldu Fisherovi a Fanku Yatesovi) slouží k náhodnému promíchání vstupního seznamu. Všechny algoritmem generované permutace se vyskytují se stejnou pravděpodobností.
Původní algoritmus
Původní verze Fisher-Yatesova algoritmu z roku 1938 byla založena na postupném výběru a vyškrtávání prvků z původního seznamu a zápisu vybraných hodnot do seznamu nového (algoritmus vykonával člověk za použití tužky a papíru).
Popis
V každém svém kroku uživatel náhodně zvolí celé číslo n na intervalu , kde
je počet dosud nevyškrtnutých prvků z prvního seznamu. Poté vždy vyškrtne z tohoto seznamu n-tý dosud nevyškrtnutý prvek a zapíše jej na konec druhého seznamu. Takto postupuje tak dlouho, dokud první seznam obsahuje nevyškrtnuté prvky.
Novodobý algoritmus
Původní procedura je sice šikovná pro ruční zpracování, ale z výpočetního hlediska je nevhodná, jelikož má kvadratickou asymptotickou složitost . Z tohoto důvodu se obvykle v programech používá modifikovaná in-place verze algoritmu s lineární asymptotickou složitostí
.
Popis
Základní myšlenka moderního algoritmu je totožná – náhodný výběr. Procedura v každém svém kroku zvolí číslo n na interavalu , kde k je počet již prohozených čísel (počet již uskutečněných iterací algoritmu) a m je délka vstupního seznamu. Prvek na indexu n (indexováno od 1) poté prohodí s prvkem na indexu m-k. Algoritmus po zamíchání všech prvků, tj. n-1 iteracích, terminuje.
Lepší asymptotické chování této verze plyne z toho, že jsou již permutované hodnoty zapisovány na konec seznamu a k dosud neprohozeným prvkům lze tedy přistupovat s konstantní časovou složitostí (původní algoritmus vyžadoval iteraci kvůli již zpracovaným hodnotám).
Vizualizace
Kód
/**
* Moderni verze Fisher-Yatesova algoritmu
* @param array pole indexovane od 0
*/
function fisherYates(array)
for i in <array.length - 1, 1> do
index = náhodné číslo z intervalu <0, i)
prohoď(array[i], array[index])
/**
* An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
* Permutes the given array
* @param array array to be shuffled
*/
public static void fisherYates(int[] array) {
Random r = new Random();
for (int i = array.length - 1; i > 0; i--) {
int index = r.nextInt(i);
//swap
int tmp = array[index];
array[index] = array[i];
array[i] = tmp;
}
}
/**
* An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
* Permutes the given array
* @param array array to be shuffled
*/
static void FisherYates(int[] array)
{
Random r = new Random();
for (int i = array.Length - 1; i > 0; i--)
{
int index = r.Next(i);
//swap
int tmp = array[index];
array[index] = array[i];
array[i] = tmp;
}
}
/**
* An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
* Permutes the given array
* @param array array to be shuffled
*/
function fisherYates(array) {
for (var i = array.length - 1; i > 0; i--) {
var index = Math.floor(Math.random() * i);
//swap
var tmp = array[index];
array[index] = array[i];
array[i] = tmp;
}
}