Fisher-Yates-Shuffle erklärt: Wie der Zufallsgenerator fair mischt

Wenn du beim Namens Picker auf den Button drückst und eine Liste von Namen mischen lässt, läuft im Hintergrund ein Algorithmus, der seit 1938 immer wieder neu entdeckt wird und sich seitdem nicht verändert hat. Er heißt Fisher-Yates-Shuffle, in der modernen Variante auch Knuth-Shuffle oder Durstenfeld-Shuffle. Was an ihm besonders ist: Er ist trivial einfach, läuft in linearer Zeit und produziert garantiert faire Ergebnisse. Alle drei Eigenschaften zusammen sind keine Selbstverständlichkeit, wie wir gleich sehen.

Was Fisher-Yates eigentlich macht

Stell dir vor, du hast eine Liste mit fünf Namen: Anna, Ben, Clara, David, Emma. Du willst sie zufällig mischen, ohne dass eine bestimmte Position bevorzugt wird. Der Fisher-Yates-Shuffle macht das so: Er fängt am Ende der Liste an, also bei Emma. Er würfelt eine Zufallszahl zwischen 0 und 4 (also Index 0 bis 4, weil Emma auf Index 4 sitzt). Sagen wir, die Zufallszahl ist 1. Dann tauscht er Emma mit dem Element auf Index 1, also Ben. Die Liste sieht jetzt so aus: Anna, Emma, Clara, David, Ben.

Jetzt geht er einen Schritt nach links, zu Position 3 (David). Er würfelt eine Zufallszahl zwischen 0 und 3. Sagen wir, die Zufallszahl ist 0. Er tauscht David mit Anna. Liste: David, Emma, Clara, Anna, Ben. Weiter zu Position 2 (Clara). Zufallszahl zwischen 0 und 2, sagen wir 2 (also bleibt sie stehen). Position 1 (Emma): Zufallszahl zwischen 0 und 1, sagen wir 0, tausche mit David. Liste: Emma, David, Clara, Anna, Ben. Fertig. Die Position 0 wird nie mehr angefasst.

Was hier passiert: Jede Position wird genau einmal mit einer Zufallszahl aus dem korrekten Bereich gefüllt. Das ist der Trick. Der Bereich wird kleiner, weil schon “gefüllte” Positionen rechts davon nicht mehr in Frage kommen. Mathematisch ergibt sich daraus, dass jede der n! möglichen Permutationen mit exakt der gleichen Wahrscheinlichkeit von 1/n! herauskommt.

Warum die naive Variante mit sort() unfair ist

Im Netz findet man immer wieder den Tipp, einen Array könne man auch so mischen:

array.sort(() => Math.random() - 0.5);

Sieht harmlos aus, ist es aber nicht. Das Problem liegt in der Vergleichsfunktion. Sortier-Algorithmen wie Timsort (in V8) oder Mergesort erwarten eine Funktion, die konsistent ist: Wenn A kleiner als B und B kleiner als C, dann muss A auch kleiner als C sein. Das nennt man Transitivität. Wenn die Vergleichsfunktion stattdessen zufällig antwortet, ist Transitivität nicht garantiert.

Was passiert dann? Der Sortier-Algorithmus läuft trotzdem durch, weil JavaScript hier nicht meckert. Aber das Ergebnis ist verzerrt. Konkret zeigen Experimente, dass mit der naiven Variante manche Permutationen deutlich häufiger auftauchen als andere. Bei einer Liste von zehn Namen kann das heißen, dass bestimmte Reihenfolgen zwei- oder dreimal so wahrscheinlich sind wie andere. Für eine echte Auslosung wäre das ein Skandal.

Die Fisher-Yates-Implementierung in JavaScript

Der Code ist überschaubar. So sieht die Standard-Variante mit crypto.getRandomValues() aus:

function shuffle(array) {
  const result = [...array];
  for (let i = result.length - 1; i > 0; i--) {
    const buf = new Uint32Array(1);
    crypto.getRandomValues(buf);
    const j = buf[0] % (i + 1);
    [result[i], result[j]] = [result[j], result[i]];
  }
  return result;
}

Drei Dinge passieren hier. Erstens: Die Liste wird kopiert, damit das Original nicht verändert wird. Zweitens: Die Schleife läuft rückwärts vom letzten Index bis Index 1. Drittens: Für jeden Index i wird ein Zufallsindex j zwischen 0 und i gewählt, und die beiden Elemente werden getauscht.

Eine Feinheit am Rand: Die Modulo-Operation buf[0] % (i + 1) ist streng genommen nicht perfekt gleichverteilt, weil 2^32 nicht durch jeden möglichen Wert von (i + 1) glatt teilbar ist. Für Listen unter einer Million Namen ist der Bias aber so klein, dass er statistisch nicht messbar wäre. Wer es ganz genau will, nutzt eine Rejection-Sampling-Variante.

Warum O(n) so wichtig ist

Linear bedeutet: Verdoppelt sich die Eingabe, verdoppelt sich die Laufzeit. Das klingt selbstverständlich, ist es aber nicht. Das Original-Fisher-Yates von 1938 arbeitete mit zwei Listen, einer Eingabe und einem Ergebnis. Jede Ziehung erforderte ein Streichen in der Eingabeliste und ein Einfügen in der Ergebnisliste. Das Streichen aus einer Liste der Länge n braucht im Schnitt n/2 Verschiebungen. Über alle n Ziehungen ergibt das O(n²).

Richard Durstenfeld hat 1964 in seinem Algorithm 235 für die Communications of the ACM gezeigt, dass man das einsparen kann: indem man direkt in der Eingabeliste tauscht, statt eine zweite Liste zu pflegen. Diese In-Place-Variante ist heute der Standard und in praktisch jeder Programmiersprache eingebaut oder als Standard-Library verfügbar. In Python ist es random.shuffle(), in Java Collections.shuffle(), in Ruby Array#shuffle. Alle nutzen unter der Haube Fisher-Yates-Durstenfeld.

Die Frage nach der Zufallsquelle

Fisher-Yates ist nur so fair wie seine Zufallsquelle. Wenn der Zufall verzerrt ist, ist auch das Mischen verzerrt. Es gibt zwei gängige Quellen im Browser: Math.random() und crypto.getRandomValues(). Math.random() liefert pseudo-zufällige Zahlen, also Zahlen, die deterministisch aus einem internen Zustand berechnet werden, der beim Start des Browsers initialisiert wird. In V8 ist das ein xorshift128+, der statistisch gleichverteilt ist, aber theoretisch vorhersagbar wäre, wenn man genug Output sieht.

crypto.getRandomValues() ist die kryptographisch sichere Variante. Sie zapft den Zufallsgenerator des Betriebssystems an, der wiederum physikalisches Rauschen aus Hardware-Quellen mit aufnimmt: Mausbewegungen, Tastatur-Timing, Netzwerk-Interrupts, auf modernen CPUs auch dedizierte Zufalls-Hardware. Das Ergebnis ist nicht vorhersagbar, auch nicht für jemanden, der den vollen Output über lange Zeit beobachtet.

Für eine Tombola, eine Schul-Auslosung oder ein Wichtel-Programm ist Math.random() vollkommen ausreichend. Für jede Ziehung, bei der echte Preise oder Geld im Spiel ist, würde ich aus Vorsicht crypto.getRandomValues() nehmen. Der Mehraufwand ist null, das Sicherheitsplus ist messbar. Mehr dazu findest du im Ratgeber zu crypto vs Math.random.

Wie man Fairness selbst testet

Wer dem Algorithmus nicht traut, kann ihn empirisch testen. Schreib eine Schleife, die zum Beispiel 100.000 Mal die Liste [A, B, C, D, E] mischt und für jede der 120 möglichen Permutationen zählt, wie oft sie vorkommt. Bei einem fairen Shuffle sollte jede Permutation rund 833 Mal auftauchen, mit einer kleinen Schwankung um diesen Wert. Bei der naiven sort()-Variante siehst du sofort, dass manche Permutationen 1.500 Mal vorkommen und andere nur 400 Mal.

Dieses Experiment ist in JavaScript in zehn Zeilen geschrieben und auf jedem Laptop in einer Sekunde durch. Mike Bostock hat dazu eine schöne interaktive Visualisierung gebaut, die im Quellen-Abschnitt unten verlinkt ist. Wer kein Vertrauen mag, sondern Beweis: Da ist er.

Anwendungsfälle jenseits von Auslosungen

Fisher-Yates begegnet dir öfter, als du denkst. Karten-Spiele wie Solitär oder Online-Poker mischen ihre Karten-Decks mit Fisher-Yates. Streaming-Dienste wie Spotify nutzen abgewandelte Shuffle-Varianten für die Wiedergabe-Reihenfolge, mit zusätzlicher Sorgfalt, dass nicht zwei Songs derselben Künstlerin direkt hintereinander kommen (ein Anti-Cluster-Algorithmus auf Basis von Fisher-Yates).

In Machine-Learning-Pipelines wird Fisher-Yates benutzt, um Trainings-Daten zu randomisieren, bevor sie in den Lerner gehen. Wenn du ein neuronales Netz auf strukturierten Daten trainierst und die Daten in der Original-Reihenfolge lässt, lernt das Netz die Reihenfolge mit. Mit Fisher-Yates wird die Reihenfolge zufällig, das Netz lernt nur die echten Muster. In Python-Bibliotheken wie scikit-learn ist das das Default-Verhalten.

Auch in der Statistik kommt Fisher-Yates zum Einsatz: bei Permutations-Tests, bei Bootstrap-Verfahren, bei Monte-Carlo-Simulationen. Überall, wo du eine endliche Datenmenge zufällig anordnen musst, ohne ihre Werte zu verfälschen.

Was hängenbleibt

Der Fisher-Yates-Shuffle ist seit 1938 unverändert der richtige Weg, eine Liste fair zu mischen. In der modernen Durstenfeld-Variante läuft er in linearer Zeit und passt in vier Zeilen Code. Der einzige Stolperstein ist die Versuchung, stattdessen array.sort(() => Math.random() - 0.5) zu nutzen, was verzerrte Ergebnisse liefert. Wer Fisher-Yates mit einer ordentlichen Zufallsquelle wie crypto.getRandomValues() kombiniert, hat eine Auslosung, die mathematisch und praktisch nicht zu schlagen ist. Genau das macht der Namens Picker.