(perfektes) Mischen nach Fisher-Yates aka
Perfect Shuffle
Definition
Gegeben sei eine Menge von gleichartigen Elementen, zum Beispiel sowas:
Delphi-Quelltext
1:
2:
3:
4:
| type
TArrayElement = Integer;
TArray = array of TArrayElement; |
Wie kann man die Elemente so anordnen (=mischen), dass eine zufällige Reihenfolge erreicht wird?
Optimal wäre eine Vorgehensweise, bei der alle Elemente die gleiche Chance auf eine neue Position haben (=perfekte Mischung oder perfekte Permutation).
Unter dem Begriff Permutation versteht man die Veränderung der Anordnung einer Menge durch Vertauschen ihrer Elemente. Dabei wird kein Element entfernt, hinzugefügt oder verändert. So gesehen ist eine Sortierung eine spezielle Permutation, bei der die Elemente in einer bestimmten Reihenfolge angeordnet sind (z.B. aufsteigende Element-Werte).
Das bringt uns auf die Idee, den Algorithmus zum "Sortieren durch Auswahl" einfach "umzukehren", um eine zufällige Anordnung der Elemente zu erreichen:
Prinzipalgorithmus: Vertausche die Position jedes Elements e[i] einer Menge mit N Elementen mit e[RandomRange(i,N)]. Das könnte in Delphi so aussehen:
Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
| procedure ShuffleFisherYates(var aArray: TArray);
var
i,j: Integer;
tmp: TArrayElement;
begin
for i := Low(aArray) to High(aArray) do begin
j := i +Random(Length(aArray) -i +Low(aArray));
tmp := aArray[j];
aArray[j] := aArray[i];
aArray[i] := tmp;
end;
end; |
Dieser Ansatz geht zurück auf R. A. Fisher and F. Yates aus dem Jahre 1938. Der Algorithmus hat einen linearen Aufwand O(n), also eine sehr gute Laufzeit, und erzeugt sogar perfekte Permutationen.
Weitere Informationen:
www.nist.gov/dads/HT...herYatesShuffle.html
Hinweis: Hier im Forum wurde der Algorithmus auch unter Miller-Yates Mischung vorgestellt, in der Literatur habe ich allerdings keinen Hinweis auf den Namen "Miller" gefunden (vielleicht hat er/sie ja geheiratet...
).
Anwendung
Klassischerweise für das Mischen einer Menge bekannter Elemente, analog zum Mischen der Karten in einem Kartenspiel. Bei der Umsetzung in einem Programm ist es in der Regel deutlich einfacher, die sortierte Menge der Elemente zu erzeugen (zum Beispiel mit einer Schleife) und dann nur noch zu mischen. Nebenbei ist die so erzeugte Permutation perfekt, was zum Beispiel beim wiederholten Ziehen (doppelter) zufälliger Elemente nicht so ist.
Konkretes Beispiel im Detail: Lotto, 6 aus 49. Häufig trifft man auf diesen Ansatz:
- eine zufällige Zahl aus dem Bereich 1..49 bestimmen
- die Zahl verwerfen, wenn sie bereits gezogen wurde
- bis keine Duplikate mehr auftreten
Bei dieser Vorgehensweise entsteht nur leider keine perfekte Permutation, weil eine Auswahl der zufällig erzeugten Zahlen stattfindet!
Obendrein hat dieser Ansatz eine unbekannte Laufzeit, da ja nicht fest steht, wie oft eine Zahl erneut gezogen werden muss.
Der Ansatz entspricht auch gar nicht dem realen Lotto, denn dort steht die Menge der zur Verfügung stehenden Zahlen ja bereits fest, die Kugeln sind schon passend bedruckt. Es geht eigentlich um die Reihenfolge, in der die Zahlen gezogen werden.
Ansatz für eine perfekte Lotto-Permutation 6 aus 49: Menge der Zahlen 1..49 in einem Feld erzeugen, dann mit dem Fisher-Yates-Verfahren mischen und die ersten 6 Zahlen des Feldes verwenden.
In Anhang befindet sich ein entsprechendes Beispielprogramm zu diesem Thema.
cu
Narses
//EDIT: Code nach einem Hinweis von
ub60 angepasst.
![Antworten [gesperrt]](./graphics/navbar/reply.png)
