[Borland C] Random getallen maken loopt vast*

[nhimf]

Ik heb een heel vaag probleem. Het zit zo:
Als ik de onderstaande code uitvoer en als max een grote waarde opgeef dan lijkt het alsof het programma vast loopt.
Ik heb met de debugger gekeken en het bleek dat hij in een oneindigende loop komt. Ik heb al met ShowMessage gekeken of het aan de while loop lag maar das nie zo, want om een gegeven moment komt die niet eens meer tevoorschijn.
Dus op de een of andere vage manier komt ie in een oneindigende loop. (niet altijd en niet op hetzelfde moment)
Kan iemand me hier misschien mee helpen?

code:

void TForm1 :: giveRandomNumbers (int min, int max)
{
  randomize();
  nrs = new int [gewensteAantal];
  for ( int i = 0; i < gewensteAantal; i++ )
  {
    nrs[i] = (random(max - min) + 1) + min;
    for ( int j = 0; j < i; j++ )
    {
    while ( nrs[j] == nrs[i] );
    {
     if ( nrs[i] == max )
        nrs[i] = (random(max - min) + 1) + min;
      else
        nrs[i] += 1;
    }
    }
  }
}

ps. Als iemand betere en/of snellere code weet vind ik het ook goed .
Ik moet dus een array vullen met een reeks random gekozen waardes en alle getallen mogen maar 1x voorkomen.

[jelmervos]

Dit is GEEN Delphi meneer de topic veranderaar.

[nhimf]

lol wilde net zeggen
ik ben bezig met Borland C Builder 4

[Anoniem: 15854]

Aan je algoritme kan het volgens mij niet liggen, want die geeft bij mij (in Delphi ) geen problemen. [met Min = 9999; Max = 99999999; Aantal = 5000; en dan 100x geprobeerd]

In je algoritme zit wel een fout; als een nrs[i] gelijk is aan nrs[j] [met j > 0], verander je nrs[i]; dan is het mogelijk dat nrs[i] gelijk is aan een nrs[k] met k<j.

Je kunt denk ik beter een gesorteerde lijst gebruiken, en daar dan een binairy-search opdoen.

Delphi code:

code:

function GetInsertPosition(AList: TList; const AValue: Integer): Integer;
var
  Mid, Top: Integer;
begin
  { Binairy search op AList naar waarde AValue,
    AValue niet in AList: 
    Result := Plaats waar AValue in AList geinsert moet worden
    AValue wel in AList:
    Result := -1
  }
  Result := 0;
  if AList.Count = 0 then Exit;

  Top := AList.Count;
  while Result + 1 <> Top do
  begin
    Mid := (Result + Top) div 2;
    if Integer(AList[Mid]) < AValue then
    Result := Mid
    else if Integer(AList[Mid]) = AValue then
    begin
    Result := -1;
    Exit;
    end
    else
    Top := Mid;
  end;
  { Laatste waarde nog bekijken }
  if Integer(AList[Result]) < AValue then
    Inc(Result)
  else if Integer(AList[Result]) = AValue then
    Result := -1;
end;

procedure GiveRandomNumbers2(const Min, Max, Count: Integer; AList: TList);
var
  Value, Index: Integer;
begin
  AList.Clear;
  while AList.Count < Count do
  begin
    repeat
    Value := (Random(Max - Min) + 1) + Min;
    Index := GetInsertPosition(AList, Value);
    until Index <> -1;
    AList.Insert(Index, Pointer(Value));
  end;
end;

[edit]
Wellicht iets beter:

code:

function GiveRandomNumbers3(const Min, Max, Count: Integer; AList: TList):
Boolean;
var
  Value, Index: Integer;
  Start: Integer;
begin
  AList.Clear;
  while AList.Count < Count do
  begin
    Value := (Random(Max - Min) + 1) + Min;
    Index := GetInsertPosition(AList, Value);
    if Index = -1 then
    begin
    Start := Value;
    repeat
      Inc(Value);
      if Value > Max then Value := Min;
      Index := GetInsertPosition(AList, Value);
    until (Index <> -1) or (Value = Start);
    if Value = Start then
    begin
      Result := False;
      Exit;
    end;
    end;
    AList.Insert(Index, Pointer(Value));
  end;
  Result := True;
end;

[dusty]

Titel was mijn fout

Moet blijkbaar voortaan verder lezen dan TForm1

[Anoniem: 17989]

Kan het niet heel simpel?

Je geeft alle elementen een random waarde.

Je sorteert die array.

Dan geef je met die volgorde iedereen een index.

Dus:

i waarde array
1 sjonny
2 marco
3 lunatic
4 olav

geef random nummer:

i waarde array ran
1 sjonnyc 0.33
2 marco 0.56
3 lunatic 0.10
4 olav 0.07

Sorteer:

4 olav
3 lunatic
1 sjonny
2 marco

en reindex:

i index
4 olav 1
3 lunatic 2
1 sjonny 3
2 marco 4

Nu heeft iedereen een uniek random nummer.


in pseudocode:

* de eeste 1 kolom bevat de waarde van het array.


array[,2]=random.
sort (array) by kolom 2

do j=1,last_row
array[j,2]=j
do end.


Korter kan niet, denk ik.

[Anoniem: 15854]

Dat werkt alleen als max-min+1 = gewensteAantal

[Anoniem: 17989]

huh, leg eens uit?

[Anoniem: 15854]

Stel ik wil een lijst met 2 waarden in de range 0..1000. Hoe doe je dat op jouw manier?

[Anoniem: 17989]

Op woensdag 20 maart 2002 11:36 schreef DiFool het volgende:
Stel ik wil een lijst met 2 waarden in de range 0..1000. Hoe doe je dat op jouw manier?

Ehh,dus: je hebt 2 entries in je array, en je wilt dat ze een random getal krijgen tussen 0 en 1000, en perse niet hetzelfde.

Waarom wil je dat het tussen 0 en 1000 ligt voor 2 entries in je array?

Waarom red je het niet met 1 en 2?

[Anoniem: 15854]

Weet ik veel.. Is niet mijn probleem

Wil alleen maar zeggen dat het dan niet werkt..

[nhimf]

Wat ik dus wilde is dat ik van een geheel (bijv 0 t/m 1000) random een selectie maak waarvan alle getallen uniek zijn maar wel random gekozen

Maar ik zal ff kijken naar de bovenstaande tips.
Thx iig.

[nhimf]

wat olav zegt werkt wel je neemt dan alleen de eerste 2 elementen van het array en je hebt dan 2 unieke random gekozen waarden uit een universum van 1000 getallen

[Dash2in1]

Ben absoluut geen algoritme-held .. maar werkt dit niet?
(c++ heeft boolean of bool?!
met random(max) bedoel ik de maximale random waarde,
houdt geen rekening met een onderwaarde)

code:

boolean inUse=new boolean[max];
int numberList=new int[max];
int tmpRnd;
for(int i=0; i<max;i++)
{
  inUse[i]=0;
}
randomize();
for(int i=0; i<max; i++)
{
  while(inUse[tmpRnd=random(max)]);
  
  numberList[i]=tmpRnd;
  inUse[tmpRnd]=1;
}

[Soultaker]

Als het alloceren van 'max' bytes geheugen geen probleem is, zou ik 't zo doen:

code:

int list[MAX], n;
for(n=0;n<MAX;++n) list[n]=n;
for(n=0;n<N;++n)
{
  int m=random()%(MAX-n)+n, other=list[m];
  list[m]=list[n]; list[n]=other;
}

Waarna de eerste N elementen van list de gevraagde getallen bevatten.

Als je minder geheugen wil gebruiken, kom je denk ik niet onder een kwadratisch algoritme uit. Ik vind dat je eigenlijk de eindigheid van je algoritme niet moet laten afhangen van de grillen van random().

Je wil trouwens iets anders doen dan 'random()%xxx' maar ik heb even geen zin om dat te verzinnen.

[Anoniem: 17989]

Op woensdag 20 maart 2002 13:21 schreef nhimf het volgende:
je neemt dan alleen de eerste 2 elementen van het array en je hebt dan 2 unieke random gekozen waarden uit een universum van 1000 getallen

Die opmerking snap ik niet.

Wat mijn methode doet is:

Je hebt een lijst met x elementen. Die x elementen krijgen allemaal een uniek nummer, waarbij al die nummers opvolgend zijn.

Dus, stel je hebt 10 elementen, dan krijgen die elementen allemaal een waarde tussen de 0 en de 11, waarbij elke waarde maar 1 keer voorkomt.

Dit is iets anders dan wat ik opvat uit:

je neemt dan alleen de eerste 2 elementen van het array en je hebt dan 2 unieke random gekozen waarden uit een universum van 1000 getallen

[nhimf]

wat jij doet is zegmaar het husselen van een aantal getallen. Wat ik bedoelde te zeggen is: dat je van de gehusselde getallen ook alleen de eerste paar kan gebruiken, heb je toch random getallen

[RickN]

Op woensdag 20 maart 2002 14:12 schreef Soultaker het volgende:
Als het alloceren van 'max' bytes geheugen geen probleem is, zou ik 't zo doen:

code:

int list[MAX], n;
for(n=0;n<MAX;++n) list[n]=n;
for(n=0;n<N;++n)
{
  int m=random()%(MAX-n)+n, other=list[m];
  list[m]=list[n]; list[n]=other;
}

Waarna de eerste N elementen van list de gevraagde getallen bevatten.
[..]

Ik vond dit wel een mooie methode, tot ik erachter kwam dat ie fout was . Deze methode geeft namelijk random getallen in de range [0..MAX] ipv [MIN..MAX]. Ik heb daarom Soultakers idee genomen en dat wat aangepast tot een methode die wel werkt.

code:

int list[max-min+1], temp;
for (int i=0; i<(max-min+1); i++) list[i]=i;
for (int i=0; i<(max-min+1); i++)
{
  int m=random(max-min);
  temp=list[i];
  list[i]=list[m];
  list[m]=temp;
};
for (int i=0; i<gewensteAantal; i++) list[i]+=min;

Nu staan je random getallen in de eerste posities van list. Deze versie alloceerd ook maar (max-min+1) integers ipv max.

Dit is niet getest, dus ik kan hier en daar een indexje fout hebben staan.

[nhimf]

Op woensdag 20 maart 2002 13:47 schreef Dash2in1 het volgende:
Ben absoluut geen algoritme-held .. maar werkt dit niet?
(c++ heeft boolean of bool?!
met random(max) bedoel ik de maximale random waarde,
houdt geen rekening met een onderwaarde)

code:

boolean inUse=new boolean[max];
int numberList=new int[max];
int tmpRnd;
for(int i=0; i<max;i++)
{
  inUse[i]=0;
}
randomize();
for(int i=0; i<max; i++)
{
  while(inUse[tmpRnd=random(max)]);
  
  numberList[i]=tmpRnd;
  inUse[tmpRnd]=1;
}

THX man!!! Deze functie is echt heel snel en werkt perfect!!!! Geen gehang meer en super snel.
Je heb me dag goed gemaakt

btw kep em iets aangepast en nu kan je er wel een minimum in stoppen.

code:

  bool * inGebruik;
  inGebruik = new bool[max];
  int * getallen;
  getallen = new int[gewensteAantal];
  int randomGetal;
  for ( int i = 0; i < max; i++ )
  {
    inGebruik[i] = false;
  }

  randomize();
  ProgressBar->Min = 0;
  ProgressBar->Max = gewensteAantal;
  for ( int i = 0; i < gewensteAantal; i++ )
  {
    do
    {
    randomGetal = random(max - min) + min;
    }
    while ( inGebruik[randomGetal] );
    getallen[i] = randomGetal;
    inGebruik[randomGetal] = true;
    ProgressBar->Position++;
  }

[Dash2in1]

At your service

Trouwens, vraag me af of die functie van RickN niet werkt of dat die bv. minder snel is oid ...
Heb geen mogelijkheid om dat zelf te testen.

edit:

Overigens als sidenote .. je bent op deze manier, zoals boven al gezegd wordt, wel afhankelijk van random hoe lang hij er over doet.

[RickN]

Op donderdag 21 maart 2002 07:13 schreef Dash2in1 het volgende:
At your service

Trouwens, vraag me af of die functie van RickN niet werkt of dat die bv. minder snel is oid ...
Heb geen mogelijkheid om dat zelf te testen.

[..]

Als gewensteAantal groot is en dicht in de buurt komt van max-min dan zal jouw methode aanmerkelijk trager worden dan die van Soultaker/mij. Overigens moet ik zeggen dat ik vóór dit topic zelf jouw methode gebruikt zou hebben.

[Dash2in1]

Wat mij wel benieuwd maakt naar het omslagpunt eigenlijk.

[Soultaker]

Het leek mij vanzelfsprekend dat getallen in het gebied 20 tot 30 genereren equivalent is met het genereren van getallen van 0 tot en met 10. Ik had zelf bedacht om een eventueel minimum bij de initialisatie van list[n] op te tellen; MAX moet dan geinterpreteerd worden als het aantal getallen in het gebied en niet zozeer als het maximum van het gebied (wellicht was een andere variabelenaam beter geweest).

De methode van RickN voldoet echter ook prima (is zelfs ietsjes efficienter) hoewel ik 'm iets minder duidelijk vind.

De reden dat ik deze methode in zijn algemeenheid mooier vind dan die van Dash2in1 (die ik overigens zelf ook vaak heb toegepast en in de praktijk meestal prima voldoet) is dat je in theorie niet kan garanderen dat random() binnen een zeker eindig aantal aanroepen een getal genereert dat je nog niet eerder hebt gehad. Dat zorgt ervoor dat de complexiteit van het algoritme in theorie oneindig groot is. Met de andere methode heb je dat probleem niet, aangezien random() precies N keer aangeroepen wordt.

Wat betreft iteratieslagen is het omslagpunt bereikt wanneer random() een enkel dubbel getal genereert. Voor executietijd zal je waarschijnlijk moeten benchmarken (en dat verschilt dan weer per compiler) maar ik denk dat wanneer het aantal getallen dat je zoekt minstens de helft van het totale aantal getallen is, dat mijn methode sneller is (hoewel dit puur een schatting is).

edit:
(never mind)