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

Schau komplizierter aus, als ich es eigentlich haben wollte 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 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.