Autor Beitrag
Hiprog
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 25

WIN XP Professional(SP2)
Delphi 7 Enterprise
BeitragVerfasst: So 15.04.07 21:16 
Hi.

Gibt es eine Möglichkeit bei Delphi eine Zahl aus dem Random Befehl zu entfernen?

Damit meine ich, dass wenn man um Beispiel aus random(30) die Zahl 3 bekommt, dass diese nicht wieder benutzt wird?
Und gibt es danach eine Möglichkeit die Zahl dann wieder anzeigen zu lassen?

Vielen Dank schon mal im voraus.
Marc.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1876
Erhaltene Danke: 129

Win 8.1, Xubuntu 15.10

BeitragVerfasst: So 15.04.07 21:50 
Das Thema hatte wir hier schon oft, aber nun gut:
Ein Variante wäre folgende:
• Du speicherst deine Zahlen in einem Array
• überprüfst dann in einer (For-)Schleife, ob die neue Zufallszahl darin vorkommt,
• wenn ja dann lass ihn mit "repeat until" oder mit einer "while"-Schleife so lange würfeln, bist die Zahl nicht mehr in diesem Array vorkommt.

im Grunde recht simpel. :)
Karlson
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 2088



BeitragVerfasst: So 15.04.07 21:58 
Kann ich absolut nicht empfehlen diesen Weg. Viel Spass wenn 5000 Zahlen mit diesem Weg erzeugt werden sollen...

Das geht eleganter über folgenden Weg:

1.) Bei x Zufallszahlen ein dyn. Array der Länge x.
2.) Dieses Array mit einer einfachen For-Schleife fortlaufend mit den Zahlen 1 bis x füllen.
3.) Mit Random(high(Array)) auf ein Element zugreifen.
4.) Den Wert des Arrays in die Zahlenliste eintragen.
5.) Das Array-Element löschen und die Grösse des Arrays auf Grösse-1 setzen.
Marc.
ontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic starofftopic star
Beiträge: 1876
Erhaltene Danke: 129

Win 8.1, Xubuntu 15.10

BeitragVerfasst: So 15.04.07 22:02 
Für 5000 Zahlen braucht er nur ein paar Zehntel-Sekunden.
Ab 50.000 mehere Sekunden. Aber ich geb dir recht, deine ist die absolut schnellere Variante. ;)
Karlson
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 2088



BeitragVerfasst: So 15.04.07 22:50 
Jo im Normalfall braucht man solche Berechnungen ja nicht unbedingt performant. Trotzdem sollte man schon sparen wo's geht.
Hiprog Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 25

WIN XP Professional(SP2)
Delphi 7 Enterprise
BeitragVerfasst: Mo 16.04.07 05:17 
Danke erstmal.
Das sollte für ein Sudoku Programm sein und ich hab das so wie im ersten Priznzip vorgeschlagen ine twa gemacht. Das dauert bei mir dann in etwa3-4 Minuten das Spiel zu erzeugen und es hat Fehler (Zahlen kommen doppelt vor...).

Wie ist das mit dem random(high(array)) gemeint? Ist das ein besonderer Befehl oder so?
Karlson
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 2088



BeitragVerfasst: Mo 16.04.07 05:34 
Zeig mal wie du das umgesetzt hast (anhand von Code).
Karlson
ontopic starontopic starontopic starontopic starontopic starofftopic starofftopic starofftopic star
Beiträge: 2088



BeitragVerfasst: Mo 16.04.07 06:18 
Ich hab mich gerade mal damit beschäftigt und beide Varianten ausprobiert.

Meine Variante:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
procedure TForm1.Button2Click(Sender: TObject);
 procedure DeleteEl(arr: Array of Integer; index: integer);
 var i: integer;
 begin
  if index<high(arr) then begin
    for i:=index to high(arr)-1 do
     arr[i]:=arr[i+1];
  end;
end;
var arr : Array of Integer;
    a : integer;
    i : integer;
    rList : Array[0..4999of Integer;
    n1,n2 : integer;
begin
 n1:=GetTickCount;
 setLength(arr, 5000);
 for i:=0 to 4999 do
  arr[i]:=i;
 for i:=0 to 4999 do
  begin
   if (i>0then setLength(arr, length(arr)-1);
   a:=Random(length(arr));
   rList[i]:=Arr[a];
   DeleteEl(Arr, a);
  end;
 n2:=GetTickCount;
 showmessage(inttostr(n2-n1));
end;


user profile iconMarcs Variante:

ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
procedure TForm1.Button1Click(Sender: TObject);
 function InArray(a:integer; sList : array of Integer):boolean;
 var i : integer;
 begin
  result:=true;
  for i:= low(slist) to high(slist) do
   begin
    if slist[i]=a then exit;
    if sList[i]=0 then break;
   end;
  result:=true;
 end;
var i : integer;
    s : Array[0..4999of Integer;
    a : Integer;
    n1,n2 : integer;
begin
 n1:=GetTickCount;
 ZeroMemory(@s, sizeOf(s));
 for i:=0 to 4999 do
  begin
   a:=random(5000)+1;
   while not InArray(a, s) do a:=Random(5000)+1;
   s[i]:=a;
  end;
 n2:=GetTickCount;
end;


Ich hab hier jetzt einfach Zufallszahlen von 1 bis 5000 produziert, so konnte ich nämlich ZeroMemory zum Initalisieren des Arrays nutzen, was wesentlich schneller als vergleichbares ist.

Hm. Meine Variante benötigt immerhin noch 47 ms, während Marcs Varianten 125 ms benötigt. Ehrlich gesagt hätte ich mir einen grösseren Unterschied vorgestellt. Wobei mehr als 75% bei grossen Datenmengen natürlich schon okay ist.

Ich müsste mal mehrere Durchlaufzeiten überprüfen. Das Problem an Marcs Algorithmus ist ja das er zeitlich zu einem gewissen Anteil auf Zufall basiert.

Das Problem an meiner Variante ist das Löschen des Array-Elements. Da geht ein Haufen Zeit verloren.

Evt. ginge es mit einer StringList statt einem Array sogar schneller. Muss ich evt. auch mal ausprobieren. Aber jetzt geh ich erstmal arbeiten. ;)
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 16.04.07 08:05 
Was Du benötigst ist eine zufällige Permutation der Zahlen von 1..N.

Also: Array mit Zahlen füllen, per Zufall mischen (nach Fisher-Yates) und dann sind die Zahlen in einer zufälligen Reihenfolge. Dann einfach nacheinander die Zahlen aus dem Array lesen und fertig.

So mischt man ein Array A (0..Count-1) mit Fisher-Yates
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
Procedure ShuffleFisherYates (Var A : Array Of Integer; Count : Cardinal);
Var
  I, T : Cardinal;
  
Begin
  For I := 0 to Count-1 do begin  
    J := I+random(Count-I);  
    T := A[J];  
    A[J] := A[I];  
    A[I] := T;  
  End;  
End;

Und so bekommt man dann eindeutige Zufallszahlen (jede Zahl 1..N nur 1x):
ausblenden Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
Var
  A : Array Of Cardinal;
  Cnt : Integer;

Procedure MyRandomize (Count : Cardinal);
Var
  I : Cardinal;

Begin
  Randomize;
  SetLength (A, Count);
  For i:=0 to Count - 1 do A[i] := I+1;
  ShuffleFisherYates (A, Count);
  Cnt := Low (A);
End;

Function MyRandom : Cardinal;
Begin
  if Cnt > High (A) Then
    Raise Exception.Create ('Alle Zahlen wurden gezogen');
  Result := A[Cnt];
  Inc (Cnt);
End;


user profile iconMarc. hat folgendes geschrieben:
Das Thema hatte wir hier schon oft, aber nun gut:

Stimmt, aber garantiert nicht mit Deiner Variante. Wenn Du nun schon so daher kommst, dann hättest Du die o.g. Variante (oder zumindest die theoretischen Grundlagen, sprich 'zufällige Permutation') erwähnen müssen. Offensichtlich liest Du nur die Fragen, aber nie die Antworten ... :roll:
user profile iconMarc. hat folgendes geschrieben:

...
im Grunde recht simpel. :)

Nein, sondern trivial. Und im Vergleich zur o.g. Methode seeeeehr langsam. Deine Variante ist vom Aufwand O(n^2), o.g. Methode vom Aufwand O(n), mithin optimal.

_________________
Na denn, dann. Bis dann, denn.
Narses
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starhalf ontopic star
Administrator
Beiträge: 10183
Erhaltene Danke: 1256

W10ent
TP3 .. D7pro .. D10.2CE
BeitragVerfasst: Mo 16.04.07 09:29 
Moin!

Dazu gibt´s mittlerweile auch einen FAQ-Beitrag. ;)

cu
Narses

_________________
There are 10 types of people - those who understand binary and those who don´t.
alzaimar
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starofftopic star
Beiträge: 2889
Erhaltene Danke: 13

W2000, XP
D6E, BDS2006A, DevExpress
BeitragVerfasst: Mo 16.04.07 09:38 
Ahoj, Narses.

Hab ich gelesen (und deine Anmerkung bezüglich des 'Miller', der offensichtlich geheiratet hat :lol: , auch).

_________________
Na denn, dann. Bis dann, denn.
Hiprog Threadstarter
ontopic starontopic starontopic starontopic starontopic starontopic starontopic starontopic star
Beiträge: 25

WIN XP Professional(SP2)
Delphi 7 Enterprise
BeitragVerfasst: Di 17.04.07 02:51 
Ich habe so etwas im Prinzip wie Karlsson geschrieben hat gebraucht. Ich brauche auch nicht so wirklich eine Permutation, obwohl die Idee auch nicht schlecht ist. Wie gesagt ich wollte ein Sudoku Programm programmieren (Wie so viele Leute in diesem Forum) aber halt mit einer anderen Variante. Aber ich denke, dass ich es jetzt hinbekommen werde, Vielen Dank an alle, die geholfen haben. Falls es weitere Probleme gibt schreib ich sie weiter hier rein, ich lasse diesen Threat also erstmal offen, bis es fertig ist.