Effiziente Erzeugung, nicht gleicher Zufallszahlen

[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.