Keine doppelten Zufallszahlen mehr

[kurtm1]

Ich möchte ein Array mit Zufallszahlen füllen, wobei keine doppelt auftreten darf. Bis jetzt habe ich folgenden Code, es befindet sich aber irgendein Fehler drinnen, da ich noch doppelte Elemente bekomme.

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var a:Array [1..10] of Byte;
var b, x, Hilf:byte;
begin
        ListBox1.Clear;

        a[1]:=random(10)+1;

        for b:=2 to 10 do
        begin
        hilf:=random(10)+1;
                for x:=1 to b do
                begin
                if hilf=a[x] then
                repeat
                hilf:=random(10)+1
                until hilf<>a[x];
                end;
                a[b]:=Hilf;
        end;

        for b:=1 to 10 do
        ListBox1.Items.Add(inttostr(a[b]));
end;

thx im voraus

[Khabarakh]

Delphi-Quellcode:

for x:=1 to b do

IMO sollte das so aussehen:

Delphi-Quellcode:

for x := 1 to b - 1 do

PS: Wenn du schon so überdimensionale Einrückung verwendest, dann benutze sie bitte auch richtig :wink: .

[edit]Der eigentliche Fehler:
Wenn eine Zahl schon enthalten ist, generierst du eine neue. Du prüfst aber nur, ob sie mit a[i] übereinstimmt, nicht aber mit den Elementen 0..i-1.
Optimiert:
Du generierst eine Zufallszahl und prüfst, ob sie in den bisherigen Elementen vorhanden ist. Sobald das zutrifft, brichst du die Schleife ab und generierst eine neue, usw.
Die Implementierung überlasse ich dir :zwinker: .

[WoGe]

Wenn ichs richtig sehe sollen 10 Zufallszahlen im Bereich 1..10 ohne doppelte erzeugt werden.
Dann kannst du auch ein Liste mit 10 Elementen anlegen und immer ein zufällig ausgewähltes in dein Array übertragen. Dieses dann löschen und aus der verbleibenden Liste wieder eins auswählen.

Die Zahl zum Auswählen muss auch entsprechend verkleinert werden.

Vorteil: gar keine Vergleiche notwendig

mfg
wo

[kurtm1]

@ Khabarakh
Deine Lösung mit dem "-1" ändert nichts, doppelte sind noch immer enthalten

//EDIT: @WoGe:
Ich hab hier nur Zufallszahlen von 1..10 genommen, damit man schneller sieht ob es doppelte gibt.

[Khabarakh]

Ich bin mal einer spontanen Idee gefolgt:
http://www.delphipraxis.net/internal...ct.php?t=56988

[edit]@WoGe: Genau, so habe ich es auch gemacht :thumb: ! [/edit]

[alzaimar]

Was Du brauchst, ist eine zufällige Permutation der Folge 0 1 2 3 4 5 6 7 8 9.
Die Idee von WoGe ist also die Richtige.

Eine zufällige Permutation erzeugt man normalerweise so, in linearer Zeit (nach Fisher-Yates):

Delphi-Quellcode:

Const  
 Count = 10;  
Var  
 A : Array[0..Count-1] of Integer;  
 I, J, T : Integer;  
begin  
 For I := 0 to Count-1 do  
  A[I] := I;  
 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

Der Code wurde von 'delfiPhan' in diesem Thread im delphi-forum gepostet.
http://www.delphi-forum.de/viewtopic...112&highlight=

[kurtm1]

@ Topic: Anscheinend ist noch nicht zu 100% klar geworden was ich brauche:
Es sollen in einem Array 10 Zufallszahlen, die im Bereich 1..100 liegen, stehen, und zwar ohne doppelte Zahlen.

[alzaimar]

aha

Delphi-Quellcode:

Var
  l : Array [0..9] Of Integer;
  r,i : Integer;

Begin
  For i := 0 to 9 do 
    Repeat
      a[i] := Random (100);                        // Randomzahl einfügen
      j := 0;  
      while a[j]<>a[i] do inc (j);             // Die gleiche Zahl suchen
    Until i=j; // Wenn die gleiche Zahl an Pos i steht, ist sie eindeutig
// Hier sind in a[0..9] eindeutige Zufallszahlen.
End;

Oder auch einfach mal den Code von delphifan modifizieren ....

Delphi-Quellcode:

const 
  Count = 10; 
Var 
  A : Array[0..Count-1] of Integer; 
  I, J, T : Integer; 
begin 
  For I := 0 to Count-1 do 
    A[I] := Random (100); // <--- Das wars, Faulpelz ;-)
  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;

[kurtm1]

die 2. variante liefert wieder doppelte Elemente

[alzaimar]

Peinich, ja, vergiss es...

[Khabarakh]

Jetzt ist meine Variante im Vorteil :mrgreen: :

Delphi-Quellcode:

procedure RandomArray(var AArray: array of Integer; const AStart, AStep, ACount: Integer);
var
  List: TList;
  i, Index: Integer;
begin
  if ACount < Length(AArray) then
    raise EInvalidArgument.Create('ACount muss größer/gleich der Länge von AArray sein');
  List := TList.Create;
  try
    i := AStart;

    repeat          // erst alle Werte in die Liste packen, ...
      List.Add(Pointer(i));
      Inc(i, AStep);
    until i = AStart + AStep * ACount;

    for i := Low(AArray) to High(AArray) do  // ...dann zufällig einen rauspicken
    begin
      Index := Random(List.Count);
      AArray[i] := Integer(List.Items[Index]);
      List.Delete(Index);
    end;

  finally
    List.Free;
  end;
end;

(EInvalidArguement ist in "Math" deklariert)
Falls niemand wieder einen Super-Algorithmus vorlegt, werde ich diesen Code morgen in den Library-Thread posten :wink: .

[Flocke]

@Khabarakh: Deine Methode hat den Nachteil, dass die Werte immer denselben Abstand haben, also nicht wirkliche Zufallszahlen zwischen 1 und 100 sind, sondern z.B. 12, 22, 32, 42 usw.

Der Algorithmus von alzaimar war IMHO besser, allerdings hat er die Veränderung an der falschen Stelle eingebaut.

Delphi-Quellcode:

Const 
  Count = 100;  // <-- hier 100
Var 
  A : Array[0..Count-1] of Integer; 
  I, J, T : Integer; 
begin 
  For I := 0 to Count-1 do 
    A[I] := I;  // <-- hier lassen 
  For I := 0 to Count-1 do 
  begin 
    J := I+random(Count-I); 
    T := A[J]; 
    A[J] := A[I]; 
    A[I] := T; 
  end; 
  // und dann einfach nur die ersten 10 Elemente aus dem Array nehmen!
end;

[kurtm1]

@alzaimar: deine variante funzt eh

Zitat:

Zitat von alzaimar

aha

Delphi-Quellcode:

Var
  l : Array [0..9] Of Integer;
  r,i : Integer;

Begin
  For i := 0 to 9 do 
    Repeat
      a[i] := Random (100);                        // Randomzahl einfügen
      j := 0;  
      while a[j]<>a[i] do inc (j);             // Die gleiche Zahl suchen
    Until i=j; // Wenn die gleiche Zahl an Pos i steht, ist sie eindeutig
// Hier sind in a[0..9] eindeutige Zufallszahlen.
End;

Diese Variante funktioniert dafür aber perfekt

[alzaimar]

@Khabarakh: Deine Version verwendet zu viele Klassen (äh, Eine :zwinker:) Bäh
@Flocke: Gut gesehen

Fazit: Flockes Modifizierung liefert den schnellsten Algorithmus, da O(n). Meiner und der von Khabarakh sind O(n^2).