Zufallslisten-Mischer - Kostenfreies Online-Tool zum Zufallssortieren

Was ist ein Zufalls-Listenmischer?

Ein Zufalls-Listenmischer ist ein Werkzeug, das eine Liste von Einträgen nimmt und sie in einer neuen, zufälligen Reihenfolge wieder ausgibt. Man gibt Namen, Aufgaben oder beliebige andere Einträge ein, einen pro Zeile, und das Werkzeug ordnet sie so um, dass jede mögliche Reihenfolge die gleiche Chance hat. Es verwendet den Fisher-Yates-Algorithmus, ein bekanntes Verfahren zur Erzeugung unverzerrter zufälliger Reihenfolgen.

So verwenden Sie den Zufallslistenmischer

1. Geben Sie die Liste in das Feld ein oder fügen Sie sie dort ein, jeweils einen Eintrag pro Zeile.
2. Klicken Sie auf „Liste randomisieren“. Die Einträge werden sofort neu angeordnet.
3. Lesen Sie die gemischte Liste unter der Schaltfläche in ihrer neuen, nummerierten Reihenfolge.
4. Klicken Sie erneut auf „Liste randomisieren“, um eine neue, unabhängige Mischung zu erzeugen.
5. Klicken Sie auf „Ergebnis kopieren“, um die neue Reihenfolge zu kopieren, oder auf „Leeren“, um von vorn zu beginnen.

Leere Zeilen in der Eingabe werden automatisch entfernt, sodass zusätzliche Zeilenumbrüche keine leeren Einträge in den Ergebnissen erzeugen.

Wie funktioniert der Fisher-Yates-Shuffle?

Der Fisher-Yates-Mischalgorithmus durchläuft die Liste einmal, beginnend beim letzten Eintrag und in Richtung Anfang. Bei jedem Schritt wählt er zufällig einen Eintrag aus dem noch nicht platzierten Teil der Liste aus und vertauscht ihn mit dem Eintrag an der aktuellen Position.

Formel des Fisher-Yates-Mischalgorithmus

Für eine Liste mit n Einträgen, deren Positionen von 0 bis zur Position n − 1 nummeriert sind:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

Die Schleife wird n − 1-mal ausgeführt, daher benötigt die Mischung insgesamt ungefähr n Schritte. Das wird als lineare Laufzeit bezeichnet und mit O(n) geschrieben. Da der Algorithmus jede Position genau einmal berücksichtigt und aus einer schrumpfenden, genau definierten Menge von Einträgen auswählt, hat jede der n! möglichen Anordnungen (n-Fakultät: n × (n − 1) × ... × 1) die gleiche Wahrscheinlichkeit, als Ergebnis zu erscheinen.

Beispiel: Mischen einer Liste mit vier Einträgen

Beginnen wir mit vier Einträgen an den Positionen 0 bis 3: Apfel, Banane, Kirsche, Dattel.

• i = 3: Die zufällige Auswahl ist j = 0. Die Positionen 3 und 0 werden vertauscht → Dattel, Banane, Kirsche, Apfel
• i = 2: Die zufällige Auswahl ist j = 2. Das Vertauschen einer Position mit sich selbst ändert nichts → Dattel, Banane, Kirsche, Apfel
• i = 1: Die zufällige Auswahl ist j = 0. Die Positionen 1 und 0 werden vertauscht → Banane, Dattel, Kirsche, Apfel

Endgültige Reihenfolge: Banane, Dattel, Kirsche, Apfel.

Bei vier Einträgen gibt es 4! = 24 mögliche Reihenfolgen. Jede davon, auch diese, hat bei jeder Mischung eine Chance von 1 zu 24.

Warum nicht einfach zufällige Paare vertauschen?

Ein einfacher wirkendes Verfahren, bei dem zwei zufällige Positionen gewählt und vertauscht werden und das mehrfach wiederholt wird, wirkt zufällig, ist es aber nicht. Einige frühe Mischprogramme arbeiteten so und bevorzugten unbemerkt bestimmte Reihenfolgen, obwohl kein einzelner Durchlauf auffällig aussah. Der Fisher-Yates-Algorithmus vermeidet das, weil jeder Eintrag genau einmal verschoben wird, und zwar auf eine Position, die aus einer genau schrumpfenden Menge von Möglichkeiten gezogen wird. Dadurch ist jede endgültige Reihenfolge gleich wahrscheinlich.

Woher stammt der Fisher-Yates-Mischalgorithmus?

Die Statistiker Ronald Fisher und Frank Yates beschrieben das Verfahren 1938 in einem Buch mit statistischen Tabellen, um beim Planen von Experimenten von Hand zu mischen. 1964 passte Richard Durstenfeld es für Computer an, sodass eine Liste an Ort und Stelle umgeordnet werden konnte, ohne eine zweite Liste für die noch verbleibenden Einträge zu benötigen. Donald Knuth nahm diese Computerversion in sein Buch The Art of Computer Programming von 1969 auf, weshalb sie manchmal Knuth-Mischung genannt wird.

Häufige Verwendungszwecke eines Zufallslistenmischers

• Festlegen der Reihenfolge, in der Schülerinnen und Schüler im Unterricht präsentieren oder Fragen beantworten
• Auslosen eines Turnierbaums oder Festlegen der Zugreihenfolge in einem Spiel
• Aufteilen einer Gruppe in zufällige Teams
• Auswählen eines Restaurants, Films oder einer Aufgabe aus einer Auswahlliste, ohne eine Möglichkeit zu bevorzugen

Eine einfache Mischung ist nicht immer die passende Lösung. Wenn einige Einträge häufiger erscheinen sollen als andere, eignet sich eine gewichtete Auswahl besser. Wenn jede Kategorie garantiert vertreten sein muss, ist eine geschichtete Stichprobe besser geeignet als ein einmaliges zufälliges Mischen.

Häufig gestellte Fragen

Ist die Mischung wirklich zufällig?

Das Werkzeug stützt sich auf den Pseudozufallszahlengenerator (PRNG) des Webbrowsers, eine Formel, die Zahlenfolgen erzeugt, die sich für praktische Zwecke wie Zufall verhalten. Das genügt für die Reihenfolge im Unterricht, für die Setzliste eines Turniers oder für die Wahl eines Films. Für Kryptografie, Glücksspielsysteme oder alles, wo Geld oder Sicherheit von Unvorhersagbarkeit abhängt, ist es nicht ausgelegt; dafür sind zertifizierte Zufallszahlengeneratoren nötig.

Sendet das Werkzeug meine Liste an einen Server?

Die Mischung selbst läuft vollständig im Browser mit JavaScript, sodass zum Neuordnen der Liste keine Netzwerkanfrage erforderlich ist. Die aktuelle Liste wird außerdem in die Webadresse der Seite geschrieben, sodass sie beim Neuladen oder in einem Lesezeichen nicht verloren geht. Wird diese Adresse kopiert, geteilt oder erneut geöffnet, wird die Liste mit ihr weitergegeben, auch an den Server, der die Seite später lädt. Wenn dies relevant ist, sollten Sie keine vertraulichen Informationen in die Liste aufnehmen.

Was geschieht mit doppelten Einträgen?

Doppelte Einträge bleiben erhalten. Wenn „Sam“ zweimal in der Eingabe vorkommt, erscheint der Name auch in der gemischten Ausgabe zweimal, möglicherweise an unterschiedlichen Positionen.

Gibt es eine Begrenzung für die Anzahl der Einträge, die ich mischen kann?

Das Werkzeug hat keine fest eingebaute Begrenzung. Da die Mischung in linearer Zeit abläuft, werden selbst lange Listen auf jedem modernen Gerät in einem Sekundenbruchteil neu angeordnet.

Wie unterscheidet sich Mischen vom Sortieren?

Beim Sortieren werden Einträge nach einer festen Regel angeordnet, etwa alphabetisch, und dieselbe Eingabe ergibt immer dasselbe Ergebnis. Beim Mischen werden Einträge zufällig angeordnet, sodass fast jedes Mal eine andere Reihenfolge entsteht, selbst bei identischer Eingabe.

Kann ich dieselbe Liste mehr als einmal mischen?

Ja. Jeder Klick auf „Liste randomisieren“ führt den Algorithmus erneut und unabhängig von jeder früheren Mischung aus. Bei einer kleinen Liste kann zufällig dieselbe Reihenfolge erneut entstehen; bei einer größeren Liste wird das äußerst unwahrscheinlich.

Referenzen

1. National Institute of Standards and Technology. Dictionary of Algorithms and Data Structures: Fisher-Yates shuffle. NIST DADS, Fisher-Yates shuffle — der Algorithmus vertauscht jedes Element mit einem zufälligen Element aus dem verbleibenden Bereich und läuft in linearer Zeit; Fisher und Yates, 1938; Durstenfeld, 1964.
2. MDN Web Docs (Mozilla). Math.random(). MDN, Math.random() — Pseudozufallszahlen im Browser sind nicht kryptografisch sicher.