Effiziente Erzeugung, nicht gleicher Zufallszahlen

[s.h.a.r.k]

Hallo zusammen,

ich habe mir gestern Abend ein Problem näher angesehen, zu dem ich keine bessere Lösung gefunden habe, als die, die hier gepostet. Aufgabe: Es sollen N Zufallszahlen generiert werden, die nich gleich sind. Hintergrund ist, dass ich aus einem Array N, zufällig ausgewählte Werte extrahieren will und da brauche ich eben verschiedene Zufallszahlen. Ja, ich weiß, man kann das Problem auch anders angehen, es geht hier aber um eine allgemeine Lösung, da man diese dann z.B. auch für Lotto einsetzen könnte.

Hier mal ein wenig Pseudocode, wie ich es im Moment machen würde:

Code:

Zufallszahlen := []
While Length(Zufallszahlen) < N do
  ZZ := GeneriereZufallszahl(Range)
  if (not ZufallszahlVorhanden(Zufallszahlen, ZZ))
    Zufallszahlen.Add(ZZ)

Sollten Fragen dies bzgl. auftauchen, ann einfach sagen, aber ich denke es sollte einigermaßen klar sein. Der Range-Parameter entspricht dem aus der Delphi-Random()-Funktion.

Das Problem hierbei ist ja, dass vor allem für kleine Range-Werte der Algorithmus sehr oft laufen kann, da je kleiner Range ist, die Wahrscheinlichkeit für eine Kollision steigt. Ich sehe einzig und allein bei der Funktion ZufallszahlVorhanden() Optimierungspotential und zwar in Form einer sehr effizienten Suche. Meine Idee ist hier, dass Zufallszahlen eine Hashmap ist und so die Suche in O(1) statt findet.

Kann man das noch besser gestalten?

[himitsu]

- du nehmen Array oder Liste
- füllen diese mit allen möglichen Zahlen
- dann wird diese Liste gemischt
- nun kann man die Liste durchgehn und hat immer eine andere Zahl

- oder man nehme eine Liste fülle sie mit allen Zahlen
- nehmen sich jeweils, per Zufall, eine Zahl raus und lösche sie
- ...

[Satty67]

himitsu's Variante #1 scheint am einfachsten

Delphi-Quellcode:

Count := Length(A);
for i := Low(A) to High(A) do
  XChange(i, Low(A) + Random(Count);

[s.h.a.r.k]

Hab hier mal den passenden Code dazu, in so fern das mal jemand anderer brauchen sollte. Habe die von himitsu genannte erste Technik verwendet, d.h. ein Array befüllt, dann durchgemixt -- zufällig versteht sich -- und dann die ersten Count Elemente ausgegeben.

Delphi-Quellcode:

function GetUniqueRandomNumbers(const Count, AFrom, ATo: Integer): TArray<Integer>; overload;

  procedure Swap(var A: TArray<Integer>; const IndexA, IndexB: Integer);
  var
    Tmp : Integer;
  begin
    Tmp := A[IndexA];
    A[IndexA] := A[IndexB];
    A[IndexB] := Tmp;
  end;

var
  Values : TArray<Integer>;
  L : Integer;
  i : Integer;
begin
  if (Count < 1) then
    SetLength(Result, 0)
  else begin
    if (ATo < AFrom) then
      raise EArgumentException.CreateFmt('AFrom (%d) has to be smaller than ATo (%d).', [AFrom, ATo]);
    L := ATo - AFrom + 1;
    if (Count > L) then
      raise EArgumentException.CreateFmt('Range from AFrom (%d) to ATo (%d) has to be greater than Count (%d).', [AFrom, ATo, Count]);
    SetLength(Values, L);
    for i := 0 to L - 1 do
      Values[i] := AFrom + i;
    Randomize();
    for i := 0 to L - 1 do
      Swap(Values, i, Random(L));
    SetLength(Result, Count);
    Move(Values[0], Result[0], Count * SizeOf(Integer));
  end;
end;

function GetUniqueRandomNumbers(const Count, Range: Integer): TArray<Integer>; overload;
begin
  Result := GetUniqueRandomNumbers(Count, 0, Range - 1);
end;

[BUG]

Das könnte dich interessieren: Kongruenzgenerator

Zitat:

In diesem Fall erzeugt der Generator jede Zahl von 0 bis m − 1 genau einmal und beginnt dann wieder von vorn. Er liefert also eine pseudozufällige Permutation dieser Zahlen.

[s.h.a.r.k]

Zitat:

Zitat von BUG (Beitrag 1099982)

Das könnte dich interessieren: Kongruenzgenerator

Zitat:

In diesem Fall erzeugt der Generator jede Zahl von 0 bis m − 1 genau einmal und beginnt dann wieder von vorn. Er liefert also eine pseudozufällige Permutation dieser Zahlen.

Schau komplizierter aus, als ich es eigentlich haben wollte :stupid: Aber ich werde mir das heute Abend mal durchlesen, vielleicht taugt das ja wirklich was. Danke für den Tipp! Die zwei Durchgänge (also einmal das Befüllen und dann das Mixen) gefallen mir bisher nicht so wirklich. Aber ist auf jeden Fall schon mal besser als vorher!

[Jumpy]

Mal nochmal ein anderer Ansatz, bei dem die Überprüfung auf vorherige Werte schnell geht.

Delphi-Quellcode:

const obereGrenze = 20;
const Anzahl = 5;

procedure TForm1.Button1Click(Sender: TObject);
var
  Liste : Array of Integer;
  i,a : Integer;
begin
  Edit1.Text:='';
  SetLength(Liste,obereGrenze);
  Randomize;
  i:=0;
  while i < Anzahl do
    begin
    a:=Random(obereGrenze);
    if Liste[a]<>1 then
      begin
      Liste[a]:=1;
      Inc(i);
      end;
    end;
  //Ausgabe:
  for i:=0 to ObereGrenze-1 do
    if Liste[i]=1 then Edit1.Text:=Edit1.Text+','+IntToStr(i);
end;

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

Zitat von himitsu (Beitrag 1100012)

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

Zitat:

Liste : Array of Integer;

Nicht man, ich:oops:
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 :stupid:

@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 :gruebel: 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:

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:

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:

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:

Zitat von s.h.a.r.k (Beitrag 1100091)

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. :thumb:
Und ja, mein Code war nur so aus dem Stegreif hingeschrieben und enthält wohl Fehler.