Fisher-Yates-shuffle

Voorbeeld van het schudden van vijf letters met de Fisher-Yates-shuffle

De Fisher-Yates-shuffle is een algoritme voor het genereren van een willekeurige permutatie van een eindige reeks. Anders gezegd: het algoritme "schudt" de reeks. Het algoritme steekt als het ware alle elementen in een hoed, en het bepaalt het volgende element door willekeurig een element uit de hoed te trekken totdat er geen elementen meer over zijn. Het algoritme produceert een onbevooroordeelde permutatie: elke permutatie is even waarschijnlijk. De moderne versie van het algoritme is efficiënt: de tijd is evenredig met het aantal items dat wordt geschud.

De Fisher-Yates-shuffle is vernoemd naar Ronald Fisher en Frank Yates, die het voor het eerst beschreven, en staat ook bekend als de Knuth-shuffle naar Donald Knuth. Een variant van de Fisher-Yates-shuffle, bekend als het algoritme van Sattolo, kan worden gebruikt om willekeurige cyclische permutaties van lengte n te genereren in plaats van willekeurige permutaties.