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

Pencil-and-paper method

As an example, we'll permute the numbers from 1 to 8 using Fisher and Yates' original method. We'll start by writing the numbers out on a piece of scratch paper:

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

Now we roll a random number k from 1 to 8—let's make it 3—and strike out the kth (i.e. third) number (3, of course) on the scratch pad and write it down as the result:

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

Now we pick a second random number, this time from 1 to 7: it turns out to be 4. Now we strike out the fourth number not yet struck off the scratch pad—that's number 5—and add it to the result:

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

Now we pick the next random number from 1 to 6, and then from 1 to 5, and so on, always repeating the strike-out process as above:

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

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