Effiziente Erzeugung, nicht gleicher Zufallszahlen

[shmia]

Beim Mischen, also dem gezielten in Unordnungbringen einer sortierten Liste, muss man aufpassen!!
Wenn man falsch mischt, dann ist das Ergebnis mathematisch nicht sauber.
Richtig wird's nur mit Fisher-Yates-Shuffle

Grundprinzip:
Jede Position im Array darf nur einmal angefasst werden.

Delphi-Quellcode:

// Falsch
// ein Element IntArray[i] kann mehrfach seinen Inhalt wechseln
for i := Low(IntArray) to High(IntArray) do
  Swap(i, Random(Length(IntArray)));

// Richtig (Fisher-Yates)
for i := High(IntArray) downto Low(IntArray) do
  Swap(i, Random(i+1)+Low(IntArray)));

Er wird Random(i+1) verwendet, weil ein Element auch mit sich selbst getauscht werden darf.

[s.h.a.r.k]

Hm, habs nun doch verstanden, wie der Algo funktioniert

@shmia: Eigentlich reicht es doch aber, bis zu Low(IntArray) + 1 zu laufen?

Delphi-Quellcode:

// Richtig (Fisher-Yates)
for i := High(IntArray) downto Low(IntArray) + 1 do
  Swap(i, Random(i+1)+Low(IntArray)));

[FredlFesl]

Das unterste Element kann auch mit dem darüber vertauscht werden.

[s.h.a.r.k]

Je länger ich mir den Code anschaue, desto eher denke ich, dass der aus dem Stegreif geschrieben wurde und falsch ist, die Idee ist aber vorhanden Pauschal würde ich behaupten, dass folgendes richtig ist:

Delphi-Quellcode:

for i := High(IntArray) downto Low(IntArray) + 1 do
  Swap(i, Random(i - Low(IntArray) + 1) + Low(IntArray))); // Habe "- Low(IntArray)" ergänzt

Denn sonst kann man über den maximalen Index hinaus schießen und das ist ein Fehler! Beispiel: wenn i gleich High(IntArray) ist und Random(i + 1) seinen maximalen Wert annimmt, nämlich i, dann ist i + Low(IntArray) bei einem nicht null-basiertem Array größer als der größte Index -> BOOM.

Somit würde ich folgendes vorschlagen:

Delphi-Quellcode:

for i := Length(IntArray) - 1 downto 1 do
  Swap(i, Random(i + 1) + Low(IntArray)));

Dies müsste nun auch für nicht null-basierte Array funktionieren.

Zum Thema, warum nur bis 1 und nicht bis 0 runter: Nehmen wir mal folgendes Array:

Code:

[0, 1, 2, 3, 4, 5, 6]
                   ^

Man setze den Zeiger auf das hinterste Element und wähle ein zufälliges Element aus dem gesamten Array. Dann tausche man das ausgewählte Element mit dem hintersten. Anschließend setze man den Zeiger eines nach links und wähle ein Element aus dem Array minus das letzte Element. So verringert sich pro Schritt die Anzahl der Elemente, die der Algorithmus betrachtet jeweils um eines. Sind nur noch zwei Elemente übrig, dann brauch der Algortihmus nur noch einmal ausgeführt zu werden, da man ja nur noch einmal zufällig auswählen kann.

[FredlFesl]

Im Zweifel Googel fragen:

Zitat von Wikipedia.com:

To shuffle an array a of n elements (indexes 0..n-1):

Code:

  for i from n - 1 downto 1 do
       j <- random integer with 0 <= j <= i
       exchange a[j] and a[i]

Ich verändere i und j nicht, sondern verschiebe beim Vertausch die beiden Indexe nur um den Offset 'Low(A)'. Dann ergibt sich folgende Lösung:

Delphi-Quellcode:

For i := Length(A)-1 downto 0 do
begin
  j := Random (i + 1); // 0 <= j <= i
  Swap(i  + Low(A), j + Low(A));
end;

[Blup]

Ich bin immer noch von meinem Lösungsansatz überzeugt:

http://www.delphipraxis.net/128822-z...lung-7.html#66

[Satty67]

Zitat von s.h.a.r.k:

Delphi-Quellcode:

for i := Length(IntArray) - 1 downto 1 do
  Swap(i, Random(i + 1) + Low(IntArray)));

Zitat von FredlFesl:

Delphi-Quellcode:

For i := Length(A)-1 downto 0 do
begin
  j := Random (i + 1); // 0 <= j <= i
  Swap(i  + Low(A), j + Low(A));
end;

Beides mixed exakt identisch. Zwischenspeichern in J kann man sich sparen und downto 1 reicht wohl auch, wie s.h.a.r.k. schon ausgeführt hat.

[shmia]

Zitat von s.h.a.r.k:

Man setze den Zeiger auf das hinterste Element und wähle ein zufälliges Element aus dem gesamten Array. Dann tausche man das ausgewählte Element mit dem hintersten. Anschließend setze man den Zeiger eines nach links und wähle ein Element aus dem Array minus das letzte Element. So verringert sich pro Schritt die Anzahl der Elemente, die der Algorithmus betrachtet jeweils um eines. Sind nur noch zwei Elemente übrig, dann brauch der Algortihmus nur noch einmal ausgeführt zu werden, da man ja nur noch einmal zufällig auswählen kann.

Jupp, das ist die korrekte Beschreibung.
Und ja, mein Code war nur so aus dem Stegreif hingeschrieben und enthält wohl Fehler.