23. Januar 2022
Viele Computergames (wie etwa das Spiel «Letterjongg», das ich 2018 im Rahmen des Swiss Open Cultural Data Hackathon programmiert habe) benötigen eine Routine, die n Elemente zufällig mischt. Nun gehört ein shuffle-Algorithmus nicht zum Standardrepertoire der Websprache Javascript, sondern lediglich die Methode random() des Math-Objekts. Wie also findet eine Zufallszahl zwischen 0 und 1 den Weg zum zufälligen Mischen von Spielsteinen oder -karten?
Eine elegante Antwort formulierten 1948 die beiden britischen Mathematiker und Statistiker Ronald Fisher und Frank Yates in ihrem Standardwerk Statistical tables for biological, agricultural and medical research (3. Auflage S. 26f., bzw. 6. Auflage S. 37f.). Ihr Verfahren: Wähle zufallsbasiert ein Element eines geordneten Arrays von n Elementen und vertausche es anschliessend mit dem letzten Arrayelement. Wähle anschliessend ein weiteres Zufallselement, diesmal allerdings aus der Menge n-1, und vertausche es mit dem zweitletzten Arrayelement. Wiederhole die Prozedur sinngemäss bis zu den letzten zwei verbleibenden Elementen.
Als Beispiel dient ein Array mit der Buchstabenfolge A B C D. Eine Zufallsauswahl ergibt zum Beispiel B, das mit dem letzten Element D vertauscht wird und A D C B ergibt (vertauschte Elemente unterstrichen). Eine Zufallsauswahl aus den ersten drei Elementen ergibt A, was durch einen Tausch mit dem zweitletzten Element zu C D A B führt. Eine weitere Wahl aus zwei Elementen ergibt C, und der letzte Tausch, diesmal mit dem drittletzten Element, führt zum (nun zufallsbasierten) Endergebnis D C A B.
Gegeben sei also ein geordneter Array arr=[0,1,2...n]. Für das zyklische Verfahren benötigen wir eine n-1-mal drehende Schleife, deren Zähler i wir für einmal rückwärts ablaufen lassen. Innerhalb der Schleife wählen wir mittels der Methode Math.random()*n (bzw. in der Folge *n-1, *n-2 usw.) zufällig eine Zahl aus, runden sie mittels Math.floor() auf die nächste ganze Zahl ab und speichern sie in der Variablen j. Schliesslich vertauschen wir die jeweilige Zufallsauswahl mit dem letzten (zweitletzten, drittletzten etc.) Arrayelement arr[i-1] mittels der Variablen k als Zwischenspeicher. Das Ergebnis
function shuffle(n) {
for (i=n; i>0; i--) {
var j=Math.floor(Math.random()*i);
var k=arr[i-1];
arr[i-1]=arr[j];
arr[j]=k;
}
}
oder, noch einfacher, als Pfeilfunktion mit destructuring assignment,
shuffle=n=> {
for (i=n; i>0; i--) {
let j=Math.floor(Math.random()*i);
[arr[j],arr[i-1]]=[arr[i-1],arr[j]];
}
};
wird nun jeden geordneten Array arr mit n Elementen zufällig neu anordnen, wie das Beispiel «Letterjongg» zeigt.
