Effiziente Erzeugung, nicht gleicher Zufallszahlen

[DeddyH]

Ich hab auch noch eine Variante ohne Generics:

Delphi-Quellcode:

type
  TIntegerArray = array of integer;

procedure GetUniqueRandomNumbers(var IntArray: TIntegerArray; Value1, Value2: Integer);
var
  BiggerVal,
  SmallerVal,
  i: integer;

  procedure Swap(i1, i2: integer);
  var
    temp: integer;
  begin
    temp := IntArray[i1];
    IntArray[i1] := IntArray[i2];
    IntArray[i2] := temp;
  end;

begin
  if Value1 > Value2 then
    begin
      BiggerVal := Value1;
      SmallerVal := Value2;
    end
  else
    begin
      BiggerVal := Value2;
      SmallerVal := Value1;
    end;
  SetLength(IntArray, BiggerVal - SmallerVal + 1);
  for i := Low(IntArray) to High(IntArray) do
    IntArray[i] := SmallerVal + i;
  for i := Low(IntArray) to High(IntArray) do
    Swap(i, Random(Length(IntArray)));
end;

initialization
  Randomize;

[himitsu]

@Jumpy: warum verwendet man eigentlich einen Integer, wenn man doch einen Bollean haben will?

Zitat:

Liste : Array of Integer;

Und falls jetzt wer mit 32 Bit, Registergrößen oder sonstwas ankommt, dann eben einen LongBool.

[Jumpy]

Zitat von himitsu:

@Jumpy: warum verwendet man eigentlich einen Integer, wenn man doch einen Bollean haben will?

Zitat:

Liste : Array of Integer;

Nicht man, ich
Das war weil ich zuerst auch die Zahl da speichern wollte, sprich

Delphi-Quellcode:

if Liste[a]<>1 then
      begin
      Liste[a]:=a;
      Inc(i);
      end;

Dann beim tippen, viel mir auf, das das doppeltgemoppelt wäre und ich hab die 0/1 Variante gemacht, da ich zu faul war alles auf Boolean zu ändern. Ging ja nur um den Ansatz, das die Position im Array die Zahl repräsentiert.

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