Autor Beitrag
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10143
Erhaltene Danke: 1234

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Do 05.04.07 16:07 
(perfektes) Mischen nach Fisher-Yates aka Perfect Shuffle


Definition

Gegeben sei eine Menge von gleichartigen Elementen, zum Beispiel sowas:
ausblenden 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:
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
// perfektes Mischen nach Fisher-Yates (angelehnt an einen Vorschlag von alzaimar)
procedure ShuffleFisherYates(var aArray: TArray);
  var
    i,j: Integer;
    tmp: TArrayElement;
begin
  // alle Elemente des Feldes durchlaufen
  for i := Low(aArray) to High(aArray) do begin
    // neue, zufällig Position bestimmen
    j := i +Random(Length(aArray) -i +Low(aArray));
    // Element Nr. i mit Nr. j vertauschen (3ecks-Tausch)
    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. :shock: 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. :idea: 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 user profile iconub60 angepasst.
Einloggen, um Attachments anzusehen!
_________________
There are 10 types of people - those who understand binary and those who don´t.