Zufallszahlen im Bereich Von-Bis, ohne Zurücklegen

[grenzgaenger]

Da in letzter Zeit öfters gefragt wird, wie man Zufallszahlen ohne zurücklegen erzeugen kann, eine kleine Klasse welches dies übernimmt.

Beispiel um die Lottozahlen 6 aus 49 zu ermitteln und auszugeben:

Delphi-Quellcode:

//Demo
var
 Zfall: Tzfzozl;
begin
 Randomize;
 //Lottozahlen 6 aus 49
 zFall := Tzfzozl.Create(1, 49, 6, true);  
 try
  write('Zufallszahlen: ');
  while not zFall.EOF do
   write(zfall.Next:  3);
 finally
  zFall.Free;
 end;
 readln;
end.

Die zugehörige Klasse ist:

Delphi-Quellcode:

type 
 //Liefert die Zufallszahlen im Bereich Von-Bis ohne zurücklegen
 //Randomize muss zuvor aufgerufen sein
 //Wenn Unique = True, werden keine doppelten Zahlen in den Pool aufgenommen
 //Über Initialize kann eine Neuinitialisierung der Ziehung erfolgen
 Tzfzozl = class
  strict private
   fArray: Array of integer;
   procedure RemoveAndMix(aIndex: Integer);
   function GetCount: integer;
  public
   Constructor Create(Von, Bis, Anzahl: Integer; Unique: boolean = false);
   procedure Initialize(Von, Bis, Anzahl: Integer; Unique: boolean = false);
   property Count: integer read GetCount;
   function First: Integer;
   function Next: Integer;
   function EOF: boolean;
 end;
  
constructor Tzfzozl.Create(Von, Bis, Anzahl: Integer; Unique: boolean = false);
begin
 inherited Create;
 Initialize(von, bis, Anzahl, Unique);
end;
procedure Tzfzozl.Initialize(Von, Bis, Anzahl: Integer; Unique: boolean = false);
 function IsXinArr(Bis, X: integer): boolean;
 var
  i: integer;
 begin
  result := false;
  for i := 0 to bis do
   if fArray[i] = x then
   begin
    result := true;
    break;
   end;
 end;
var
 i, x: integer;
 canUnique: boolean;
begin
 canUnique := (bis - von) >= anzahl;
 SetLength(fArray, 0);
 if (bis > von) and CanUnique then
 begin
  setlength(fArray, Anzahl);
  for i := 0 to high(fArray) do
   if not Unique then
    fArray[i] := random(bis-von+1)+von
   else 
   begin
    repeat
      x := random(bis-von+1)+von;
    until not IsXinArr(i-1, x);
    fArray[i] := x; 
   end;
 end;
end;
function Tzfzozl.EOF: boolean;
begin
 result := length(fArray) = 0; 
end;
function Tzfzozl.First: Integer;
begin
 if count > 0 then
  result := Next
 else
  result := -1; //-1 wenn fehler aufgetreten
end;
function Tzfzozl.Next: Integer;
var
 i: integer;
begin
 result := -1;
 if not Eof then
 begin
  i := random(length(fArray));
  result := fArray[i];
  RemoveAndMix(i);
 end;
end;
function Tzfzozl.GetCount: integer;
begin
 result := length(FArray);
end;
procedure Tzfzozl.RemoveAndMix(aIndex: Integer);
 procedure Shuffle;
 var
  i, x, y: integer;
 begin
  for i := low(fArray)+1 to high(fArray) do
  begin
   y := i + Random(Length(fArray) -i);
   x := fArray[i-1];
   fArray[i-1] := fArray[y];
   fArray[y] := x;
  end; 
 end;
var
 i: integer;
begin
 for i := aIndex + 1 to high(fArray) do
  fArray[i-1] := fArray[i];
 setlength(fArray, high(FArray));
 Shuffle;
end;

das gesamte Programm ist im Anhang beigefügt.

Über den Parameter Unique kann die Erzeugung der Zahlen gesteuert werden, ob diese doppelt auftreten dürfen oder unique sein müssen.

Im Fehlerfall wird ein leeres Array zurückgegeben, bei überschreiten der Grenzen -1.

//Edit: FIndex entfernt, da intern nicht verwendet wird.

[sx2008]

Vielleicht geht es auch noch anderst:
Angenommen mein Bereich liegt zwischen 1 und 47269 (so viele User hat die DP ).
Dann wäre es doch günstiger, sich nur die gezogenen Zahlen zu merken; das braucht weniger Resourcen.
Wenn dann z.B. schon 5 Zahlen gezogen wurden, dann muss man eine Zufallszahl zwischen 1 und 47269-5 erzeugen.
Jetzt muss man aber alle schon gezogenen Zahlen berücksichtigen.
Die neue Zufallszahl heisst X.
Die Menge der gezogenen Zahlen heisst M.
Für jede Zahl in M, die kleiner oder gleich X ist, muss X um eins erhöht werden.
Damit überspringt man sozusagen alle Zahlen in M.
Nachdem man alle Zahlen in M geprüft hat, fügt man X zur Liste/array der gezogenen Zahlen hinzu und gibt X zurück.
Je mehr Zufallszahlen gezogen werden umso länger dauert der Vergleich mit M.
(es spielt keine Rolle, in welcher Reihenfolge man X den Zahlen in M vergleicht)
Bei kleinem Wertebereich ist alzaimar's Algorithmus besser; bei grossem Wertebereich hat mein Algorithmus den Vorteil deutlich resourcensparender zu sein.

Man könnte sich auch eine Kombination der beiden Algorithmen vorstellen:
Bis zu einen bestimmten Anzahl von Ziehungen merkt man sich die gezogenen Zahlen und wendet obigen Algo an.
Ab dann kopiert man die verbleibenden Zahlen in eine Liste, bringt diese in Unordnung und zieht dann nur noch aus dieser Liste.

[xZise]

Zitat von sx2008:

[...]Wenn dann z.B. schon 5 Zahlen gezogen wurden, dann muss man eine Zufallszahl zwischen 1 und 47269-5 erzeugen.

Nein... Wenn die zahlen nicht aus den Bereich 47264 - 47269 stammt. Du meintest wohl eher, das du dann so viele Zahlen noch übrig hast.

MfG
xZise

[sx2008]

Zitat von xZise:

Zitat von sx2008:

[...]Wenn dann z.B. schon 5 Zahlen gezogen wurden, dann muss man eine Zufallszahl zwischen 1 und 47269-5 erzeugen.

Nein... Wenn die zahlen nicht aus den Bereich 47264 - 47269 stammt. Du meintest wohl eher, das du dann so viele Zahlen noch übrig hast.

Nein ich erzeuge eine Zahl zwischen 1 und 47269-5 = 47264.
Angenommen Zufallszahl X wäre 47260. Die gezogene Zahlen wären 10, 401, 2008, 16666 und 20001.
Dann wird wird X 5 Mal erhöht auf 47265.
Mit dem Algorithmus wird jede Zahl zwischen Start und Ende addressiert, nur nicht die Zahlen, die schon gezogen wurden.

Also als ich darüber nachgedacht habe, hat mir das doch einige (heftige) Kopfschmerzen bereitet, aber der Algorithmus ist korrekt.

[alzaimar]

Ich frage mich gerade, was an 47.000 Zahlen so resourcenverbrauchend ist, wenn die VCL mit mehreren MByte vorlegt.
Ich bezweifle auch, das Dein Algorithmus funktioniert, vermutlich, weil ich ihn nicht verstanden habe.
Vielleicht schreibst Du ein kleines Programm, damit ich das verstehe.

[sx2008]

Zitat von alzaimar:

Ich frage mich gerade, was an 47.000 Zahlen so resourcenverbrauchend ist, wenn die VCL mit mehreren MByte vorlegt.
Ich bezweifle auch, das Dein Algorithmus funktioniert, vermutlich, weil ich ihn nicht verstanden habe.

Nun, so wie ich es erklärt habe, war es auch nicht richtig
Die ganze Sache ist viel komplizerter als ich gedacht habe.
Das überspringen der schon gezogenen Zahlen ist sehr knifflig.
Über drei Stunden musste ich kämpfen, bis es "Klick" gemacht hat.

Also der von mir vorgeschlagene Algorithmus lohnt nur dann, wenn der Wertebereich in die Millionen geht und die Anzahl der Ziehungen nicht allzu gross wird.
Ansonsten ist es ein nettes Beispiel um seine Gehirnzellen zu quälen.

[Dipl Phys Ernst Winter]

"sx2008"

Zitat:

Für jede Zahl in M, die kleiner oder gleich X ist, muss X um eins erhöht werden.
Damit überspringt man sozusagen alle Zahlen in M.

Damit bin ich überfordert, es sollte wohl heißen 'für jedes X das in M enthalten ist'.

Das Incrementieren von x erscheint mir sehr fragwürdig, da damit die Statistik verdorben wird: nach dem Ziehen einer Zahl bekommt die darauffolgende das doppelte Gewicht, da sie durch sich selbst und durch ihren Vorgänger ausgewählt wird.

Daher ist richtig: Wenn x in M enthalten ist, das heist bereits gezogen wurde, so ist neu zu würfeln.