Fisher-Yates Shuffle

Bakgrund

Fisher-Yates är en algoritm som används för att slumpmässigt omfördela innehållet i en grupp på ett sätt som fungerar ungefär som när man blandar en kortlek. Det ger minsta möjliga bias även om pseudoslumptalskällan inte är välfiltrerad och ren.

Sättet som algoritmen arbetar på fungerar ungefär som när man plockar lotter ur en tombola eller blandar en kortlek där man drar en efter en tills det inte längre finns några att dra. Rätt använd är biasen väldigt låg.

Andra namn är också the Knuth Shuffle efter matematikern Donald E. Knuth som använder denna.

Funktion

Som ett exempel skall vi permutera numren 1 till 8 genom att använda Fisher-Yates metod. Vi skriver talen på en bit papper:

Range	Roll	Scratch	Result
		1 2 3 4 5 6 7 8

Nu slumpar vi ett tal k mellan 1-8, vi kan säga att det blev 3 så vi stryker det 3:e numret från papperet och flyttar det till resultatrutan.

Range	Roll	Scratch	Result
1–8	3	1 2 3 4 5 6 7 8	3

Vi tar ett nytt slumpmässigt tal, denna gång från 1-7 som matchar de siffror vi ej har strukit. Låt oss säga att det blev 4, så vi stryker det fjärde ej redan strukna numret och flyttar det till resultatrutan.

Range	Roll	Scratch	Result
1–7	4	1 2 3< 4 5 6 7 8	3 5

Vi fortsätter på samma vis med ett nytt slumptal, denna gång från 1-6 och sedan 1-5 osv ända tills alla tal är strukna.

Range	Roll	Scratch	Result
1-6	5	1 2 3 4 5 6 7 8	3 5 7
1-5	3	1 2 3 4 5 6 7 8	3 5 7 4
1-4	4	1 2 3 4 5 6 7 8	3 5 7 4 8
1-3	1	1 2 3 4 5 6 7 8	3 5 7 4 8 1
1-2	2	1 2 3 4 5 6 7 8	3 5 7 4 8 1 6
		1 2 3 4 5 6 7 8	3 5 7 4 8 1 6 2

För att spara tid kan man byta plats med alla strukna tal och det sista talet i serien och därmed hela tiden ha en sammanhängande ordning med ostrukna tal. Se pseudokoden nedan som gör på det sättet.

Pseudokod

Randomisera n element på plats i en array

for i from n-1 down to 1 do
    j = random(0..i)
    swap a[j], a[i]
done

Initialisera en array a med n elements från en slumpmässigt ordnad kopia av source

a[0] = source[0]
for i from 1 to n-1 do
    j = random(0..i)
    a[i] = a[j]
    a[j] = source[i]
done