Random ohne Dublette

[Piper44]

Ich möchte z.B. eine Zufallszahl von 1...6 ausgeben. Kommt dann als erstes die 3, so soll sie bei dem nächsten Buttonclick nicht mehr kommen, d.h. die möglichen Zahlen, aus denen die neue Zufallszahl gebildet wird, nehmen um 1 ab, bis keine mehr vorhanden ist.
Das Grundprinzip ist mir klar - wie kann ich jedoch die Dubletten vermeiden und eine Zahl die schonmal erschienen ist nicht mehr ausgeben lassen. Danke für die Hilfe.

Delphi-Quellcode:

var
  Form1: TForm1;
  Zufall: Integer;

procedure TForm1.Button1Click(Sender: TObject);
begin
randomize;
Zufall:= random (5)+1;
Label1.Caption:=IntToStr (Zufall);
end;
end.

[edit=SirThornberry]Delphi-Tags gesetzt - Mfg, SirThornberry[/edit]

[xaromz]

Hallo,

das ist ganz einfach. Du musst Dir nur merken, welche Zahl schon gekommen ist:

Delphi-Quellcode:

var
  SchonGehabt: array [1..6] of Boolean;

// Zurücksetzen
procedure InitRandom;
var
  I: Integer;
begin
  for I := 1 to 6 do
    SchonGehabt[I] := False;
end;

// Zufallszahl erzeugen
function GetRandom: Integer;
begin
  repeat
    Result := Random(6) + 1;
  until not SchonGehabt[Result];
  SchonGehabt[Result] := True;
end;



//Aufruf:
procedure TForm1.FormCreate(Sender: TObject); 
begin 
  Randomize;
  InitRandom; 
end;

procedure TForm1.Button1Click(Sender: TObject); 
begin 
  Zufall:= GetRandom;
  Label1.Caption := IntToStr(Zufall); 
end;

Gruß
xaromz

[Robert Marquardt]

Die einfachste Methode ist das Sortieren umzukehren. Erst eine Liste von 6 Zahlen erstellen und sie dann durcheinanderbringen.
Einfach mehrfach zwei Zahlen zufaellig gewaehlt vertauschen.

[Sunlight7]

Moin!

@xaromz: Klasse Endlosschleife beim 6. Aufruf :zwinker:

Eine Möglichkeit:

Delphi-Quellcode:

var
  Index:Byte;
  Zahlen:Array [1..6] of Byte;

// Zurücksetzen
procedure InitRandom;
   var i, p1, p2, temp:Byte;
begin
   Index:=0;

   For i:=1 to 6 do
      Zahlen[i]:=i;

   For i:=1 to 100 do begin
      p1:=Random(6)+1;
      p2:=Random(6)+1;
      If p1=p2 then Continue;

      temp:=Zahlen[p1];
      Zahlen[p1]:=Zahlen[p2];
      Zahlen[p2]:=temp;
   end;
end;

// Zufallszahl erzeugen
function GetRandom(const Index:Byte):Byte;
begin
   Case Index of
      1..6: Result:=Zahlen[Index];
      else Result:=0;
   end;
end;



procedure TForm1.FormCreate(Sender: TObject);
begin
   Randomize;
   InitRandom;
end;

//Aufruf:
procedure TForm1.Button1Click(Sender: TObject);
   var Zufall:Byte;
begin
   If Index=6 then begin
      InitRandom;
      Label1.Caption:='';
   end;
   Inc(Index, 1);

   Zufall:=GetRandom(Index);
   Label1.Caption:=Label1.Caption+IntToStr(Zufall)+' ';
end;

Eine andere Möglichkeit:

Delphi-Quellcode:

var
  List:TList;

// Zurücksetzen
procedure InitRandom;
   var i, p1, p2:Byte;
       temp:PByte;
begin
   For i:=1 to 6 do begin
      New(temp);
      temp^:=i;
      List.Add(temp);
   end;

   For i:=1 to 100 do begin
      p1:=Random(6);
      p2:=Random(6);
      If p1=p2 then Continue;

      List.Exchange(p1, p2);
   end;
end;



procedure TForm1.FormCreate(Sender: TObject);
begin
   List:=TList.Create;

   Randomize;
   InitRandom;
end;

//Aufruf:
procedure TForm1.Button1Click(Sender: TObject);
   var Zufall:Byte;
begin
   If List.Count=0 then begin
      InitRandom;
      Label1.Caption:='';
   end;

   Zufall:=PByte(List[0])^;
   Dispose(List[0]);
   List.Delete(0);
   Label1.Caption:=Label1.Caption+IntToStr(Zufall)+' ';
end;

Grüßle!

[marabu]

Guten Morgen,

Zitat:

Zitat von Piper44

Ich möchte z.B. eine Zufallszahl von 1...6 ausgeben.

um den Hinweis von Robert noch einmal aufzugreifen: Hier handelt es sich weniger um eine Ziehung (6 aus 6), sondern mehr um eine Permutation. Deshalb ist das Mischen eleganter: klick

Grüße vom marabu

[negaH]

Delphi-Quellcode:

type
  TZahlen = array of Integer;

procedure Lotto(var Sortiert,Gezogene: TZahlen; Ziehungen: Integer = 6; Elemente: Integer = 49);
var
  I,J,K,N: Integer;
begin
  Sortiert := nil;  // stellt sicher das Sortiert <> Gezogene ist
  Gezogene := nil;

  if Ziehungen > Elemente then
    raise Exception.Create('Man kann nicht mehr Kugeln ziehen als in der Urne sind');

  SetLength(Sortiert, Ziehungen);
  SetLength(Gezogene, Ziehungen);

  for I := 0 to Ziehungen -1 do
  begin
    K := 0;
    N := Random(Elemente - I) + 1;
    for J := 0 to I -1 do
      if N >= Sortiert[J] then
      begin
        Inc(N);
        Inc(K);
      end else Break;
    for J := I downto K +1 do
      Sortiert[J] := Sortiert[J -1];
    Sortiert[K] := N;
    Gezogene[I] := N;
  end;
end;

Aufruf für deinen Fall dann Lotto(..,..., 6, 6);
Du kanst dir das so umbauen das der Parameter "Sortiert" als lokale Variable benuztzt wird, da du ja nur die gezogene Reihenfolge benötigst.

Gruß Hagen

PS:

Zitat:

Deshalb ist das Mischen eleganter: klick

;) Ansichtssache, mischen halt ich für eine "Brute Force" Methode.

[marabu]

Hallo Hagen,

wenn du meinem Link folgst, findest du eine Misch-Prozedur, welche für den Fall "n aus n" eine Urnenziehung (draw & remove) inplace ausführt. Nur für den Fall "n aus n" galt meine Aussage. Was daran sollte brute force sein?

Freundliche Grüße

[xaromz]

Hallo,

Zitat:

Zitat von Sunlight7

@xaromz: Klasse Endlosschleife beim 6. Aufruf :zwinker:

Erstens: Die Endlosschleife kommt erst bei der siebten Zahl. Und zweitens: Wenn er die sechs Zahlen von eins bis sechs in einer zufälligen Reihenfolge will, dann sollte er nicht nach einer siebten fragen. Setzen, sechs :zwinker: .

Gruß
xaromz

[negaH]

Zitat:

Was daran sollte brute force sein?

Wenn wir 6 zufällige Zahlen haben möchten, jede nur einmal, wie oft muß man minimal Random() aufrufen ?

Die Mischer-Methode ist deshalb nicht elegant weil sie aus meiner Sicht
1.) bei 6 Zahlen minimal 12 mal Random() aufruft.
2.) weil sie trivial ist, also das was man als normaler Programmierer als Worst-Case Lösung, wenn einem nichts anders mehr einfällt, benutzt.
Mal ehrlich unter uns, was an dieser Methode ist so besonders elegant ?

Brute Force bezog sich also auf die "Idee wie man es lösen" könnte, und Brute Force ist immer der letzte Schritt wenn alles andere keine Lösung ist.

Die "Mischer-Methode" ist dann und nur dann elegant wenn die Aufgabenstellung nicht mehr das "Ziehen von x eindeutigen zufälligen Zahlen" ist sondern das "zufällige Mischen einer Menge von x Zahlen" ist. Und selbst dann sollte man mit x Aufrufen von Random() auskommen können. In deinem Falle solltest du also das Array nur von 0 bis x-1 durchgehen und das Element an diesem Index mit einem Element an einen zufälligen Index austauschen. Denn so vermeidest du das bei einem schlechten RNG und 2 zufälligen Indizes sich das ganze Mischen wieder aufhebt. Denoch entstehen Zufalls-Indizes die gleich sind, also zb. Austauschungen von Index 2 mit 1 und Index 3 mit 1. Die Wahrscheinlichkeiten ändern sich damit und sind NICHT identisch im Vergleich bei Ziehen von x eindeutigen Zahlen. Das habe ich aber schon im "Lotto" Thread erklärt.

Sie ist aber insofern "elegant" wenn man aus der Menge der im WEB kursierenden Lösungen auswählen müsste, dann ist sie sogar schon fast super-elegant ;) Es geht aber eben noch besser aus meiner Sicht.

Gruß Hagen

[marabu]

Lieber Hagen,

Zitat:

Zitat von negaH

Wenn wir 6 zufällige Zahlen haben möchten, jede nur einmal, wie oft muss man minimal Random() aufrufen ?

die Zahlen stehen doch schon fest, 1 bis 6 sind vorgegeben!

Zitat:

Zitat von negaH

Die Mischer-Methode ist deshalb nicht elegant weil sie aus meiner Sicht
1.) bei 6 Zahlen minimal 12 mal Random() aufruft.

Meine Funktion ruft Random() nur 5 mal auf.

Zitat:

Zitat von negaH

2.) weil sie trivial ist, also das was man als normaler Programmierer als Worst-Case Lösung, wenn einem nichts anders mehr einfällt, benutzt.

Trivial ist kein Synonym für Worst-Case.

[equote="Prof. Beutelspacher in 'Das ist o.B.d.A. trivial'"]Trivial ist das Wort in mathematischen Texten, das am häufigsten falsch gebraucht wird. ... Damit bezeichnet man Argumente oder Eigenschaften, die sich ohne jedes Zutun aus einer Definition oder einem Satz ergeben. ... Bei richtigem Gebrauch des Wortes bewegt man sich auf einem schmalen Grat. Es ist manchmal eine Frage der mathematischen Vorbildung, was man als trivial bezeichnet.[/equote]
Und negativ besetzt ist der Begriff auch nicht - wie man sieht.

Zitat:

Zitat von negaH

Mal ehrlich unter uns, was an dieser Methode ist so besonders elegant ?

Die von mir verlinkte Methode arbeitet inplace und kommt mit einer minimalen Anzahl Lines-Of-Code aus.

Zitat:

Zitat von negaH

Brute Force bezog sich also auf die "Idee wie man es lösen" könnte, und Brute Force ist immer der letzte Schritt wenn alles andere keine Lösung ist.

Auch Brute-Force ist kein negativ besetzter Begriff per se. Bei einer nicht analytisch beschreibbaren Extremwertsuche verwendest auch du gerne eine Brute-Force-Methode, weil du dadurch sicher sein kannst den Extremwert zu finden.

Zitat:

Zitat von negaH

Die "Mischer-Methode" ist dann und nur dann elegant wenn die Aufgabenstellung nicht mehr das "Ziehen von x eindeutigen zufälligen Zahlen" ist sondern das "zufällige Mischen einer Menge von x Zahlen" ist.

Genau so habe ich die Aufgabe hier verstanden - und ich habe noch immer das Gefühl, dass ich das nicht alleine so sehe.

Zitat:

Zitat von negaH

Und selbst dann sollte man mit x Aufrufen von Random() auskommen können.

Einer weniger würde es auch tun...

Zitat:

Zitat von negaH

In deinem Falle solltest du also das Array nur von 0 bis x-1 durchgehen und das Element an diesem Index mit einem Element an einen zufälligen Index austauschen.

Das ist nicht zwingend - ich kann auch vom anderen Ende her mischen:

Delphi-Quellcode:

procedure Shuffle(var a: array of integer);
var
  i, j, temp: integer;
begin
  for i := High(a) downto 1 do
  begin
    j := Random(i);
    temp := a[i];
    a[i] := a[j];
    a[j] := temp;
  end;
end;

BTW: Das soll der Fisher-Yates-Shuffle sein.

Nachdenkliche Grüße