Fisher-Yates Shuffle: Skillnad mellan sidversioner

Från Täpp-Anders
Hoppa till navigering Hoppa till sök
Created page with "== 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 ..."
 
Ingen redigeringssammanfattning
 
(En mellanliggande sidversion av samma användare visas inte)
Rad 8: Rad 8:


== Funktion ==
== Funktion ==
=== Pencil-and-paper method ===


As an example, we'll permute the numbers from 1 to 8 using [[#Fisher and Yates' original method|Fisher and Yates' original method]]. We'll start by writing the numbers out on a piece of scratch paper:
Som ett exempel skall vi permutera numren 1 till 8 genom att använda Fisher-Yates metod. Vi skriver talen på en bit papper:


{| class="wikitable"
{| class="wikitable"
Rad 19: Rad 18:
|}
|}


Now we roll a random number ''k'' from 1 to 8—let's make it 3—and strike out the ''k''th (i.e. third) number (3, of course) on the scratch pad and write it down as the result:
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.


{| class="wikitable"
{| class="wikitable"
Rad 25: Rad 24:
! Range !! Roll !! Scratch !! Result
! Range !! Roll !! Scratch !! Result
|-
|-
| 1–8 || 3 || 1 2 <s><span style="color:gray;">3</span></s> 4 5 6 7 8 || 3
| 1–8 || 3 || 1 2 <s>3</s> 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:
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.


{| class="wikitable"
{| class="wikitable"
Rad 34: Rad 33:
! Range !! Roll !! Scratch !! Result
! Range !! Roll !! Scratch !! Result
|-
|-
| 1–7 || 4 || 1 2 <s><span style="color:gray;">3</span></s> 4 <s><span style="color:gray;">5</span></s> 6 7 8 || 3 5
| 1–7 || 4 || 1 2 <s>3<</s> 4 <s>5</s> 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:
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.


{| class="wikitable"
{| class="wikitable"
Rad 43: Rad 42:
! Range !! Roll !! Scratch !! Result
! Range !! Roll !! Scratch !! Result
|-
|-
| 1–6 || 5 || 1 2 <s><span style="color:gray;">3</span></s> 4 <s><span style="color:gray;">5</span></s> 6 <s><span style="color:gray;">7</span></s> 8 || 3 5 7
| 1-6 || 5 || 1 2 <s>3</s> 4 <s>5</s> 6 <s>7</s> 8 || 3 5 7
|-
|-
| 1–5 || 3 || 1 2 <s><span style="color:gray;">3</span></s> <s><span style="color:gray;">4</span></s> <s><span style="color:gray;">5</span></s> 6 <s><span style="color:gray;">7</span></s> 8 || 3 5 7 4
| 1-5 || 3 || 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> 8 || 3 5 7 4
|-
|-
| 1–4 || 4 || 1 2 <s><span style="color:gray;">3</span></s> <s><span style="color:gray;">4</span></s> <s><span style="color:gray;">5</span></s> 6 <s><span style="color:gray;">7</span></s> <s><span style="color:gray;">8</span></s> || 3 5 7 4 8
| 1-4 || 4 || 1 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> || 3 5 7 4 8
|-
|-
| 1–3 || 1 || <s><span style="color:gray;">1</span></s> 2 <s><span style="color:gray;">3</span></s> <s><span style="color:gray;">4</span></s> <s><span style="color:gray;">5</span></s> 6 <s><span style="color:gray;">7</span></s> <s><span style="color:gray;">8</span></s> || 3 5 7 4 8 1
| 1-3 || 1 || <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> 6 <s>7</s> <s>8</s> || 3 5 7 4 8 1
|-
|-
| 1–2 || 2 || <s><span style="color:gray;">1</span></s> 2 <s><span style="color:gray;">3</span></s> <s><span style="color:gray;">4</span></s> <s><span style="color:gray;">5</span></s> <s><span style="color:gray;">6</span></s> <s><span style="color:gray;">7</span></s> <s><span style="color:gray;">8</span></s> || 3 5 7 4 8 1 6
| 1-2 || 2 || <s>1</s> 2 <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> || 3 5 7 4 8 1 6
|-
|-
| &nbsp; || &nbsp; || <s><span style="color:gray;">1</span></s> <s><span style="color:gray;">2</span></s> <s><span style="color:gray;">3</span></s> <s><span style="color:gray;">4</span></s> <s><span style="color:gray;">5</span></s> <s><span style="color:gray;">6</span></s> <s><span style="color:gray;">7</span></s> <s><span style="color:gray;">8</span></s> || 3 5 7 4 8 1 6 2
| &nbsp; || &nbsp; || <s>1</s> <s>2</s> <s>3</s> <s>4</s> <s>5</s> <s>6</s> <s>7</s> <s>8</s> || 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 ==
== Pseudokod ==
Rad 82: Rad 82:


[[category:Programmering]]
[[category:Programmering]]
[[category:C]]
[[category:Algoritmer]]
[[category:Linux]]

Nuvarande version från 21 februari 2013 kl. 05.13

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
Hämtad från ”http://wiki.sikvall.se/index.php?title=Fisher-Yates_Shuffle&oldid=440”