Entwickler-Ecke

Delphi Language (Object-Pascal) / CLX - zufallszahlen nicht doppelt


hassedelphi - Di 30.12.03 16:25
Titel: zufallszahlen nicht doppelt
hi

ich will eine Menge an zahlen (a : array of Interger) durch zufall aus einer bestimmten Menge (1 bis 500) so erzeugen, dass ich keine Zahl doppelt habe. (sodass kein a[i] dem anderen a[j] vom Wert her gleicht).

ausgangssituation

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
var a : array [1..10of integer; //das array is eigentlich dynamisch

procedure tform4.zufall;
 var i : integer;
begin

 randomize;
 for i := 1 to length(a) do
  a[i]:=random(500+1);

end;


ich hab leider keine Idee. Vielleicht könnte man machen:


Delphi-Quelltext
1:
2:
3:
while not (a[1]<>a[2]) and (a[2]<>a[3]) and (a[1]<>a[3])... do begin
 //SourceCode von oben
end;


aber da das array dynamisch ist, müsste die bedingung in einer wiederhohlschleife ausgedrückte werden. geht das überhaupt?

naja, kann jmd helfen?


Christian S. - Di 30.12.03 16:54

Hm. Du könntest es so machen:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
randmize; //nur EINNMAL!


procedure fuellen;
var b : array[1..500of Boolean;
     i : Integer;
begin
  for i:=1 TO 500 b[i] := true;

  for i:=1 TO High(a) DO
  begin
    repeat
      a[i] := Random(500)+1;
    until b[a[i]] = true;
    b[a[i]] := False;
  end;
end;


Du speicherst in b also, ob eine Zahl schon verwendet wurde. Nachteil: je weniger Zahlen noch verfügbar sind, desto länger braucht der Algorithmus, um eine Zahl zu finden.

Alternative: ein dynamisches Array, welches alle verfügbaren Zahlen hält und bei Verwendung einer Zahl um eins verkleinert wird. Nachteil: ständiges Ändern der Arraygröße ist ebenfalls langsam.

MfG
Peter


catweasel - Di 30.12.03 17:04

Ich mach da meistens einen kleinen Umweg über eine Stringlist....
Die hat nämlich so schöne Methoden wie delete und so...

Zufallszahlen die sich nicht wiederholen sind mathematisch so ein "ziehen ohne zurücklegen" Problem wie wir es ja alle aus der Schule kennen....

Also.... Z.B:
Die Zahlen von 1-500 sollen in zufälliger Reihenfolge gezogen werden und dabei keine doppelt...

1. Stringliste erstellen und etwa so (PseudoCode/ syntax nur skizziert)


Delphi-Quelltext
1:
2:
3:
4:
5:
liste := TStringlist.create;
for x :=1 to 500 do
begin
liste.add(inttostr(x));  // Nun haben wir alle zahlen von 1-500
end;


und dann ziehen und das gezogene aus der Liste entfernen und aus der Restliste ziehen


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
y := 1// unser erses Arrayelement hat diesen Index

repeat
z := random(liste.count)  // Nur was noch da ist kann zufällig gezogen
                                   // werden...

meinarray[y] := strtoint(liste[z])  // das gezogene wandert ins array

liste[z].delete;    // egal wie die syntax ist.. auf jeden fall element aus
                        // der liste löschen

inc(y);             //  nächstes Mal wird das nächste Arrayfeld gefüllt

until liste.count < 1;   // wenn es nur noch 0 Elemente gibt, kann
                                //aufgehört werden.


Das sollte so (ähnlich) funktionieren.....

Catweasel

Moderiert von user profile iconPeter Lustig: Code- durch Delphi-Tags ersetzt


tomtom62 - Di 30.12.03 17:41

Also Stringlist ist gut, aber besser denke ich wäre der folgende Ansatz


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
tt: string;

Randomize;

liste1.clear;

liste1.add(inttostr(Random(500)+1));

while liste1.count < 10 do
   begin
       tt:=inttostr(Random(500)+1);
       
       if liste1.indexof(tt) <0 
       // tt ist noch nicht in der Liste enthalten
       
       liste1.add(tt);
       Application.ProcessMessages;
       // Andere Anwendungen wollen auch noch leben -)

    end;


catweasel - Di 30.12.03 18:15

tomtom62 hatte geschrieben:
Zitat:
Also Stringlist ist gut, aber besser denke ich wäre der folgende Ansatz


Dein Ansatz hat einen entscheidenden Nachteil den ich vermeiden wollte:

Deine If Abfrage:


Delphi-Quelltext
1:
2:
if liste1.indexof(tt) <0  
       // tt ist noch nicht in der Liste enthalten


Wenn man Pech hat dauert es bis man eine passende Zahl zieht, da doppelt gezogene Zahlen lediglich verworfen werden, jedoch nichts destotrotz zunächst doppelt gezogen werden....

Bei meiner Variante komme ich OHNE JEDEN VERGLEICH aus, dh.

das zeihen von n Zahlen benötigt immer exakt n Ziehungen....

Bei mir wird nämlich eigentlich nicht die Zahl gezogen, sondern die Liste mit allen Zahlen nach Zufall nur "umsortiert"..

Zitat:
Application.ProcessMessages;
// Andere Anwendungen wollen auch noch leben -)



Da man also nicht wegen "blöder" Zufallszahlen in einer Schleife hängenbleiben kann, kann man sich das auch ersparen.
Anders ausgedrückt: Das Zufallselement bestimmt nicht die Anzzahl der Iterationen des Algorhytmus...

Catweasel

P.S.: Das löschen eines Strings aus einer Stringliste ist um einiges Schneller, als das ändern einer Arraygrösse.....
In sofern vergleichbar mit Peter Lustigs zweitem Tipp, aber ohne die Bedenken wegen Performance..

P.P.S:
@ Peter Lustig

Jaja, das sind die guten Moderatoren immer soo penibel mit den Code Tags :roll:
Jetzt war ich mal penibel und nun isses doch wieder falsch? *beleidigt gugg*

Ich dachte immer die "Delphi" Code-Tags wären für Delphi Quelltexte die Syntaktisch korrekt sind, die man also auch per copy&Paste übernehmen könnte, ohne Compilerfehler zu bekommen (referenzierte Komponenten mal als vorhanden vorausgesetzt)...
Und die "Code" Code-Tags seien für andere Quellcodes wie C, JAva, Basic :lol: , etc... oder eben für Pseudo Quellcode....
Und als solchen habe ich meinen Bezeichnet.... Aaaaalso sollte die Code Tags richtig sein, oder......
Würd mich echt mal interessieren wann ihr was haben wollt.... Nervt euch ja auch das immer wieder ändern (zu müssen?)


Christian S. - Di 30.12.03 18:34

Hallo!

Zuerst einmal zu den Delphi-Tags: die sind dazu da, um das Syntax-Highlighting zu haben. Das heißt, jeder Text, bei dem Highlighting Sinn macht, sollte in diese Tags gesetzt werden. Der Einsatz der Delphi-Tags hat nichts damit zu tun, ob man den Quelltext sofort übernehmen kann oder nicht.
Mit "Sinn machen" ist natürlich auch der Fall einer anderen Programmiersprache erledigt, denn Delphi-Highlighting macht dort keinen Sinn.

Und dann habe ich noch eine Möglichkeit gefunden:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
procedure fuellen;
VAR b : Array[1..500of Integer;
    i,k, max : Integer;
begin
  for i:=1 TO 500 DO b[i] := i;
  max := 500;

  for i:=1 TO 10 DO
  begin
    k := random(max)+1;
    a[i] := b[k];

    b[k] := b[max];
    dec(max);
  end;
end;

Hier wird das Array nicht jedes Mal neu dimensioniert, sondern der maximal zulässige Index verringert. Dabei wird die gerade gerzogene Zahl im Reservoir immer durch die letzte Zahl, die noch im Reservoir steht ersetzt. Sollte ziemlich schnell sein.

MfG
Peter


hassedelphi - Mi 31.12.03 11:26

vielen dank :D


Christian S. - Mi 31.12.03 11:56

Hallo!

Würde mich mal interessieren, welche Version Du jetzt genommen hast. Damit ich einen Grund habe, beleidigt zu sein, wenn's nicht meine ist. ;-)

MfG
Peter


Thunder - Mo 05.01.04 02:42

also ich habe das in einem proggi mal so gelöst:
Counter is die Zahl die ich zum Schluss haben will und PreCounter is nurn Zwischenspeicher.
Sind beides Integer natürlich :)

Delphi-Quelltext
1:
2:
3:
4:
5:
PreCounter := Counter;
      Repeat
        Counter := Random(Listbox1.Items.Count);
      Until
        Counter <> PreCounter;


Alibi - Mo 05.01.04 04:24

Das verhindert nur, dass die direkt aufeinanderfolgenden Zahlen nicht die selben sind. Mach doch einfach ein Array und trag da alle möglichen Zahlen ein und dann mische es.
Hab das mal so gelöst:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
TPicArray = array of gluInt;
.
.
.
procedure Shuffle(var Arr: TPicArray);
var
  i,tmp: integer;
  tmpPic: gluInt;
begin
  for i := 0 to high(Arr) do
  begin
    tmp := random(high(Arr));
    tmpPic := Arr[i];
    Arr[i] := Arr[tmp];
    Arr[tmp] := tmpPic;
  end;
end;

Musst bloß statt gluInt einfach normale Integer nehmen. Hier hab ich in nem Spiel in OpenGL Texturen gemischt mit.


MKehrer - Do 08.01.04 17:10

Du kannst auch foldenden Code probieren


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
Procedure CreateRandomValues(Var a:Array of Integer);
Var i,v,index1,index2:Integer;
Begin
  For i:=0 to High(a) do a[i]:=i; //Werte vorbelegen;
  For i:=0 to 1000 do //Feld mischen
    Begin
      index1:=Random(Length(a));
      index2:=Random(Length(a));
      v:=a[index1]; a[index1]:=a[index2]; a[index2]:=v;
    End;
End;


Alibi - Do 08.01.04 17:49

??
Das ist doch das selbe in Grün?


MKehrer - Fr 09.01.04 09:48

@Alibi

Sorry, hab wohl Dein Posting übersehen


squap - Mo 29.03.04 16:44

catweasel hat folgendes geschrieben:
Ich mach da meistens einen kleinen Umweg über eine Stringlist....
Die hat nämlich so schöne Methoden wie delete und so...

Zufallszahlen die sich nicht wiederholen sind mathematisch so ein "ziehen ohne zurücklegen" Problem wie wir es ja alle aus der Schule kennen....

Also.... Z.B:
Die Zahlen von 1-500 sollen in zufälliger Reihenfolge gezogen werden und dabei keine doppelt...

1. Stringliste erstellen und etwa so (PseudoCode/ syntax nur skizziert)


Delphi-Quelltext
1:
2:
3:
4:
5:
liste := TStringlist.create;
for x :=1 to 500 do
begin
liste.add(inttostr(x));  // Nun haben wir alle zahlen von 1-500
end;


und dann ziehen und das gezogene aus der Liste entfernen und aus der Restliste ziehen


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
y := 1// unser erses Arrayelement hat diesen Index

repeat
z := random(liste.count)  // Nur was noch da ist kann zufällig gezogen
                                   // werden...

meinarray[y] := strtoint(liste[z])  // das gezogene wandert ins array

liste[z].delete;    // egal wie die syntax ist.. auf jeden fall element aus
                        // der liste löschen

inc(y);             //  nächstes Mal wird das nächste Arrayfeld gefüllt

until liste.count < 1;   // wenn es nur noch 0 Elemente gibt, kann
                                //aufgehört werden.


Das sollte so (ähnlich) funktionieren.....

Catweasel

Moderiert von user profile iconPeter Lustig: Code- durch Delphi-Tags ersetzt


hallo,
als was fuer typen muessen "meinarray" und "liste" deklariert werden ? bekomme "char und str inkompatible typen" als Fehlermeldung .
noch etwas, wie lautet die korrekte "liste[z].delete"-methode ?

danke


catweasel - So 11.04.04 17:44

Zitat:
als was fuer typen muessen "meinarray" und "liste" deklariert werden ? bekomme "char und str inkompatible typen" als Fehlermeldung .
noch etwas, wie lautet die korrekte "liste[z].delete"-methode ?



Delphi-Quelltext
1:
2:
3:
var
meinarray : array[1..500of integer;
liste : TStringlist;  // da aber das ordentliche serstellen nicht vergessen ;-)


delete für Stringlists die ja im Prinzip ein Array of String sind) und andere Arrays lauten Allgemein:


Delphi-Quelltext
1:
delete(array,recordnummer);                    


Mehr Tipps gibts in der Delphi-Hilfe oder bei Obi ;-)

Catweasel


Udontknow - Di 13.04.04 10:39

Hallo!

Warum denn Stringlisten nutzen, wenn es doch so eine schöne Integerliste [http://www.delphi-forum.de/viewtopic.php?t=18612] gibt (werbwerb). Das ist flotter als eine Stringliste, wo immer erst zwischen String und Integer hin und her konvertiert werden muss.

Cu,
Udontknow