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

[alzaimar]

Wenn man schon vom 'Ziehen' spricht, dann könnte man das doch auch genau so implementieren: Ich habe einen Topf mit N Zahlen (1..N) und ziehe jedesmal eine zufällige Zahl heraus. Klar, nach jedem Ziehen enthält der Topf eine Zahl weniger.

Delphi-Quellcode:

Function Zupfeln (Var Zahlen : TCardinalList) : Cardinal;
Var
  i : Cardinal;

Begin
  i := Random (Zahlen.Count);
  Result := Zahlen[i];
  Zahlen.Delete(i);
End;

Also, was das Umsetzen einer Vorgabe anbelangt, würde ich das für optimal und elegant halten. Aber ich will mich -um Gottes willen- nicht mit Euch anlegen, sondern nur eine Portion berliner Senf (a.k.a. Mostrich) dazugeben.

Ach ja, kommt mir nicht im schlechter Performance, bitte. :zwinker:

[negaH]

@Marabu,

tja, wieso meinst du das ich die Worte "trivial" und "brute force" als negative Worte benutzt habe. Das zeigt das du dich durch meine persönliche Meinung angegriffen fühlst, das musst du doch garnicht ;) 1.) hatte ich es nie vor und deshalb wählte ich auch diese Worte, du interpretierst sie negativ 2.) ist meine Meinung eine persönliche, quasi Geschmacksfrage, was ich auch deutlich betonte.

Wahr ist:

1.) für 6 zu ziehende eindeutige Zahlen benötigt man 5 mal den Aufruf von Random(), du hast Recht damit.
2.) beim Mischen benötigt man minimal 6 Speicher für 6 Zahlen, und das pro Ziehung = 6 mal.
3.) die bedingten Wahrscheinlichkeiten sind unterschiedlich zwischen den Verfahren, das dürfte dem Fragesteller aber wurscht sein, solange sie funktioniert
4.) für jeden Unwissenden stellt die für ihn beste Lösung eine Lösung dar die er durch "Brute Force" herausfand dar. Die Triviale Lösung ist diejenige die bei einem gewissen Wissensstand die logisch am einfachsten zu erreichende Lösung ist. Nun, Mischfunktionen sind algorithmisch linear und einfach gestrickt -> Speicher für 6 Zahlen allozieren und initialisieren, mit welchem Inhalt ist dabei egal -> Speicher per Zufall mischen -> Speicher sequientiell auslesen, welche Richtung ist egal. Also nichts sonderlich elegantes, sondern eine sehr stabile, einfach nachvollziehbare und sehr flexible Lösung, trivial halt weil sie nur wenig Grundwissen benötigt.

Sogesehen habe ich deine Lösung niemals als schlecht bezeichnet, sondern einfach nur angezweifelt das sie auch elegant ist ;) Wobei ich gleich dazu bemerkte das Eleganz eine Geschmacksfrage ist. Willst du dich wirklich über Geschmack streiten bzw. aufregen ? ;)

Zitat:

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

Das bezog sich garnicht auf deine Lösung, sondern auf die ganz simplen Mischermethoden/Vorschläge wie "erzeuge 6 mal jeweils 2 zufällige Indizes und vertausche die Elemente an diesen Indizees" (nachzulesen in diesem Thread).

Gruß Hagen

PS: meine Wortwahl ist also schon sehr gezielt gewesen. Lies meine Beiträge nochmal durch unter der Sichtweise das ich "elegant" anzweifle und "trivial"/brute force" nicht als negativ besetzte Worte sondern als "Aufwandsanalyse im Wissen" betrachte, durch. Nur du hast sie eben als negativ interpretiert, Warum?
Und achte mal darauf ob ich "die" oder "deine" Mischermethode schrieb !

[alzaimar]

Zitat:

Zitat von negaH

... trivial halt, weil sie nur wenig Grundwissen benötigt....

Wenn man trivial mit einfach gleichsetzt, dann...

Zitat:

Zitat von Erhard Blanck

Schade, daß das Wort "einfach" so einen simplen Beigeschmack hat.

und

Zitat:

Zitat von Heimito von Doderer

Ganze Sachen sind immer einfach wie die Wahrheit selbst. Nur die halben Sachen sind kompliziert.

Ich persönlich bevorzuge einfache Lösungen -speziell in der Informatik-, eine Maxime, die mir mein Vater nicht oft genug vorhält: "Keep it simple".

Nun hat das Triviale aber die Bedeutung, das es das Offensichtliche darstellt, das einem überall begegnet. Und dann ist es offensichtlich nicht trivial, bei der Frage nach 'Zufallszahlenreihen ohne Wiederholung' auf eine zufällige Permutation zu kommen: Dazu ist doch Einiges an Grundwissen nötig. Es handelt sich jedoch um die einfachste Lösung, die dann eben auch die Eleganteste ist.

Verfolgt doch diese und ähnliche Threads in diesem und anderen Programmierforen zu dem Thema: Die richtige Anwort (Permutation) wird durch die Bank von erfahrenen, also mit Grundwissen ausgestatteten Leuten gepostet. Die triviale (also offensichtliche) Lösung ist nämliche die, einfach so lange zu würfeln, bis eine Zahl kommt, die vorher noch nicht kam.

Schönes Wochenende und Gruße aus Berlin.

[negaH]

Siehst du und da unterscheidet sich mein Meinung was elegant ist erheblich von deiner.

Ausgehend von der Forderung das wir eine Urne von 6 Zahlen haben, 1 bis 6 und daraus per Zufall nun alle 6 Zahlen ziehen ergeben sich reale Erfordernisse.

1.) es ist eine zufällige Permutation
2.) es ergeben sich exakte Wahrscheinlichkeiten für jede gezogene Zahl

Elegant ist es nun exakt diese Rahmenbedingungen einzuhalten und eventuell ohne die vorherige Erzeugung der Urne auskommen zu können.
Trivial ist es diese Urne zu allozieren und daraus die 6 Zahlen per Zufall zu ziehen.
An der Realität vorbei ist es

a.) solange per Zufall eine Zahl zu erzeugen bis wir eine ziehen die wir noch nicht hatten -> verfälschte bedingte Wahrscheinlichkeiten die nocht der Realität entspricht
b.) die Urne falsch zu mischen, zb. eben 6 mal jeweils 2 Zufallsindizes erzeugen und dann diese zu vertauschen -> verfälschte bedingte Wahrscheinlichkeiten

Extrembeispiel:

Wir wollen aus 10 Milliarden Zahlen nur 3 eindeutige Zahlen ziehen. Elegent ist es die maximale Größe der Urne auf diese 3 Zahlen beschränken zu können. Unelegant ist es ein Array mit 10 Milliarden Zahlen anzulegen und dann 10 Milliarden mal diese per Zufall zu mischen.

Elegant ist also eine Lösung als Funktion die für alle möglichen Anwendungsfälle effizient funktioneren kann, auch wenn es in einem konkreten Fall nicht sofort als Vorraussetzung für diese Funktion als erfoderlich gilt. Denn so hat man eine BlackBox einmalig programmiert die wiederverwendet werden kann ohne das man sie anpassen muß.

Das ist meine Definition von elegant aus Sicht einer Einschätzung der Qualität einer Funktion, neben den Aspekten der Performance, Komplexität und Einfachheit.
"Keep it simple" ist auch eine meiner Devisen, aber nicht auf Teufel komm raus, also Kompromißbasiert (ich meine du denkst da ähnlich). Völlig falsch ist es aber sich nicht an die Rahmenbedingungen zu halten oder jedesmal eine Denkarbeit von Neuem machen zu wollen. Dann lieber beim ersten mal 25% mehr Zeit investiert und gleich was gutes erdacht.

Gruß Hagen

PS: übrigens erfüllt meine obige Funktion "Lotto" eben auch diese Anforderungen. Man kann mit ihr aus 10 Milliarden Zahlen 3 eindeutige und zufällige erzeugen und dabei die begingten Wahrscheinlichkeiten der Realität auch einhalten.Man kann aber auch ganz simpel nur 6 Zahlen aus 6 ziehen ohne das dabei die Peformance oder der Platzverbrauch schlechter wäre als bei den trivialen Lösungen.