Making a unique random list of numbers

Task: I need an algorithm that would make a list of numbers that are unique, yet fall within a certain range of numbers.  No number can be duplicated in this list.

Example: Given a range of numbers from 1 to 100, pick 20 numbers in this range at random, and store them in a list or array.  None of the 20 numbers selected can occur more than once in this list/array.

Variables will be:

1) The quantity of unique numbers needed (e.g. 20 in the above example)
2) The range of numbers (e.g, 1-100)

If the algorithm is run twice, it should not produce the same results.

Can anyone provide such an algorithm?
Who is Participating?

Commented:
As far as I can tell, this does as you requested. You set the quantity of unique numbers by setting the bounds of the array you pass to this procedure when you declare it. Range is defined as anything greater than lowrange or less then highrange.

procedure CompRandArray(var ArrayToFill: Array of Integer; LowRange, HighRange: Integer);
var
I, J: integer;
HaveDup: boolean;
begin
Randomize;
for I := Low(ArrayToFill) to High(ArrayToFill) do
begin
Repeat
ArrayToFill[I] := Random(HighRange);
Until ArrayToFill[I] > LowRange;
Repeat
HaveDup := False;
for J := Low(ArrayToFill) to High(ArrayToFill) do
begin
if (ArrayToFill[J] = ArrayToFill[I]) and (I <> J) then
begin
ArrayToFill[I] := Random(HighRange);
HaveDup := True;
break;
end;
end;
Until HaveDup = False;
end;
end;

0

Commented:
I found a problem in the above code - It will sometimes allow a value beneath the Lowrange - this will work much better and includes error code to correct for range being smaller array bounds

procedure CompRandArray(var ArrayToFill: Array of Integer; LowRange, HighRange: Integer);
var
I, J: integer;
HaveDup: boolean;
begin
Randomize;
if (HighRange - LowRange) < (High(ArrayToFill) - Low(ArrayToFill)) then
Raise ERangeError.Create('Range to small to fill given Array');
for I := Low(ArrayToFill) to High(ArrayToFill) do
begin
Sleep(0);
Repeat
ArrayToFill[I] := Random(HighRange);
Until ArrayToFill[I] > LowRange;
Repeat
HaveDup := False;
for J := Low(ArrayToFill) to High(ArrayToFill) do
begin
Sleep(0);
if (ArrayToFill[J] = ArrayToFill[I]) and (I <> J) then
begin
Repeat
ArrayToFill[I] := Random(HighRange);
Until ArrayToFill[I] > LowRange;
HaveDup := True;
break;
end;
end;
Until HaveDup = False;
end;
end;

0

Author Commented:
I commend you for your effort, but the second modified code sends Delphi 1 into a loop, and locks up the PC.  Adding Application.ProcessMessages here and there allowed me to trace through the code.  The problem is that on the selection of the last random number, the procedure is never exited.

One problem area is here:
Until ArrayToFill[I] > LowRange;

How can the actual value of the LowRange be included in the random list if you have a > rather than a >= ?

I still don't think this is the solution though, for it still never comes out of the procedure.

var
Form1: TForm1;
RandomArray : Array[0..19] of Integer;

procedure CompRandArray(var ArrayToFill: Array of Integer; LowRange, HighRange: Integer);

implementation

{\$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var
Ctr : Integer;
begin
CompRandArray(RandomArray, 1, 20);
Memo1.Clear;
For Ctr := Low(RandomArray) to High(RandomArray) do begin
end;
end;

Here I am trying to choose 20 random numbers out of a total of 20 (e.g., 1-20).
0

Commented:
Try this one - changes made

Range is now inclusive (Lowrange <= X <= Highrange)
it was exclusive (LowRange < X < Highrange)

Error code changed to reflect above

Correction made for 0-based arrays (this was your problem)

This should work now

BTW - is range of randoms and size of array are equal - this function will consistently produce the same numbers in the same order - This is a feature :) of the Random function and I cant correct it.  As long as there is 1 more value in range than in the array count, it will be truly random (as truly random as a computer can get it)

procedure CompRandArray(var ArrayToFill: Array of Integer; LowRange, HighRange: Integer);
var
I, J: integer;
HaveDup: boolean;
begin
Randomize;
if (HighRange + 1 - LowRange) < ((High(ArrayToFill) + 1) - Low(ArrayToFill)) then
Raise ERangeError.Create('Range to small to fill given Array');
for I := Low(ArrayToFill) to High(ArrayToFill) do
begin
Sleep(0);
Repeat
ArrayToFill[I] := Random(HighRange + 1);
Until ArrayToFill[I] >= LowRange;
Repeat
HaveDup := False;
for J := Low(ArrayToFill) to High(ArrayToFill) do
begin
Sleep(0);
if (ArrayToFill[J] = ArrayToFill[I]) and (I <> J) then
begin
Repeat
ArrayToFill[I] := Random(HighRange + 1);
Until ArrayToFill[I] >= LowRange;
HaveDup := True;
break;
end;
end;
Until HaveDup = False;
end;
end;
0

Commented:
BTW - if speed is an issue then take out the sleep(0) lines as they increase the run time by approximately 800%.  I put them to allow the System time to respond to other apps and such.
0

Commented:
hi  Monroe406,

a other method

var
TheArray : Array[1..20] of integer;

procedure TForm1.Button1Click(Sender: TObject);
var i : integer;
begin
Randomize;
TheArray[Low(TheArray)] := Random(100); {Set First, no Duplicates available}
for i := Low(TheArray)+1 to High(TheArray) do
begin
TheArray[i] := Random(100);
{check for Duplicates}
while TheArray[i] in [TheArray[Low(TheArray)]..TheArray[i-1]] do
TheArray[i] := Random(100);
end;
{output in a sorted Listbox}
Listbox1.clear;
for i := Low(TheArray) to High(TheArray) do
end;

meikl
0

Commented:
Ok, here is my method.... It is faster than the other routine that are here because it doesn't get a ranomd number and check if it is within the range.... it just takes a ranomd number from the HIGHRANGE-LOWRANGE and then adds the LOWRANGE to that so the formula is...

randnum := lowrange + (highrange - lowrange + 1); //+1 because it is zero based....

OK, here goes my routine.... I also wrote a SORT procedure that sorts the array of numbers and you can see that the result is exatly what you wanted... I also wrote a test program to test it and it works like a champ... it checks for the ranges also so if you make a mistake with the ranges it tells you that there is an error... very fast and convenient :)) OK, here it goes....

I just hope that if you like mine better then the rest, I'd like to get the credit... If oyu think that someone else's is better then let him/her get the credit.. 10x

It's a whole program by the way...
===============
unit Unit1;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;

type
TForm1 = class(TForm)
Button1: TButton;
l: TLabel;
l1: TLabel;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;

implementation

{\$R *.DFM}

//The random number generator.....

//lr for lowrange and hr for highrange
function RandNums(var arr : array of integer; lr, hr : Integer) : boolean;
var
i, j, r : integer;
dup : boolean;
begin
//Check if everything is alright with the ranges...
if (hr < lr) or ((hr-lr) > (high(arr) - low(arr))) then begin
ShowMessage('Range error');
result := false;
exit;
end;
randomize;
arr[low(arr)] := lr + random(hr-lr+1);
for i := Low(arr)+1 to High(arr) do begin
r := (hr - lr) + 1;
arr[i] := lr + random(r);
repeat
dup := false;
for j := Low(arr) to i-1 do
if arr[j] = arr[i] then begin
arr[i] := lr + random(r);
dup := true;
end;
until not dup;
end;
result := true;
end;

//Sort procedure that sorts the array....

procedure Sort(var arr : array of integer);
var
done   : boolean;
tmp, i : integer;
begin
repeat
done := true;
for i := Low(arr) to High(arr)-1 do begin
tmp := arr[i+1];
if arr[i] > tmp then begin
arr[i+1] := arr[i];
arr[i] := tmp;
done := false;
end;
end;
until done;
end;

//Test procedure..... Tests everything... YOu can play with the ranges and see that it announces //the errors if any...

procedure TForm1.Button1Click(Sender: TObject);
var
arr : array[1..20] of integer;
i   : integer;
begin
l.caption := '';
l1.caption := '';
if RandNums(arr, 1, 20) then begin
for i := Low(arr) to High(arr) do
l.Caption := l.caption + IntToStr(arr[i]) + '  ';
Sort(arr);
for i := Low(arr) to High(arr) do
l1.Caption := l1.caption + IntToStr(arr[i]) + '  ';
end;
end;

end.
============
I hope it helps...

-Viktor
--Ivanov
0

Commented:
Oh, and also it doesn't produce the same results... Everytime different results except if the array contains only one element and the range is from lets say 0 and 1 for lowrange and highrange respectively.... If you have any other questions please ask...

-Viktor
--Ivanov
0

Commented:
Viktornet - your code crashes when the range is less than the array bounds.
...
if (hr < lr) or ((hr-lr) > (high(arr) - low(arr))) then begin

should be changed to

if (hr < lr) or ((hr-lr) < (high(arr) - low(arr))) then begin

BTW, I dont think it is very nice to make one minor code change to my function and call it your own.  Suggesting an improvement is one thing, but I started from scratch - you didnt.  If you come up with a better function ON YOUR OWN then by all means post it and you deserve the points!
0

Commented:
When I read the question from Monroe, then I started writing the code without looking at anyones code... I looked just before I posted it so made some comments about the differences... when I was writing the comments I didn't see the comment from krez... and his way of doing it which is almost the same as mine... so actually I started from scratch also and in a few mintues I was done with the whole program and example and everything... I don't see why you call it improvment because it doesn't seem to be like yours at all.. Maybe more like kretzschmar, but now like yours....

-Viktor
--Ivanov
0

Commented:
btw- About the range check thing you're right...it should be changed to

if (hr < lr) or ((hr-lr) < (high(arr) - low(arr))) then begin

instead of the one I gave...

if (hr < lr) or ((hr-lr) > (high(arr) - low(arr))) then begin

I probably did > instead of < or something... anyway, thanks for the tip...

-Viktor
--Ivanov
0

Commented:
hi viktor, hi  heathprovost, hi Monroe406,

my comment above didn't work probably, this works better

unit rand_u;

interface

uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls;

type
TForm1 = class(TForm)
Button1: TButton;
ListBox1: TListBox;
Edit1: TEdit;
Edit2: TEdit;
procedure Button1Click(Sender: TObject);
private
{ Private-Deklarationen }
public
{ Public-Deklarationen }
end;

var
Form1: TForm1;

implementation

{\$R *.DFM}

var
MyArray : Array [1..20] of Integer;

procedure FillArrayUnique(var TheArray : array of Integer; Rand : Integer);
var
i,j : integer;
ok : Boolean;
begin
Randomize;
TheArray[Low(TheArray)] := Random(Rand); {Set First, no Duplicates available}
for i := Low(TheArray)+1 to High(TheArray) do
begin
repeat
TheArray[i] := Random(Rand);
ok := true;
{check for Duplicates}
for j := Low(TheArray) to i -1 do
if TheArray[J] = TheArray[I] then ok := False;
until ok;
end;
end;

function PadRight(SToPad : String; NToFill : Integer) : String;
var s : String;
begin
while length(s) < NToFill do s := ' ' + s;
result := s;
end;

procedure TForm1.Button1Click(Sender: TObject);
var I : Integer;
begin
FillArrayUnique(MyArray,StrToInt(edit1.text));
{output in a sorted Listbox}
Listbox1.clear;
for i := Low(MyArray) to High(MyArray) do
end;

end.

meikl
0

Commented:
Viktornet - Sorry if I was rude, I am a little irritable tonight - Have been up 16 hours working on code that I need done tomorrow, or aug... today I mean.  This site has been my only distraction :)
0

Commented:
No problem heathprovost! Wish you luck in getting the code done.. Sorry if i was rude also.... I didn't get a sleep for almost 30 hours know, so gotta get some sleep finally....

Well, kretzschmar, and all, I think we all get to the same thing almost so, Monroe could choose which one works best for him,... Happy New Year '99 to all of ya ;-)

-Viktor
--Ivanov
0

Author Commented:
To heathprovost,

I really want to thank you for all the time you put into this procedure.  Your final modifications seem to do the job well.

I sure wish I could reward you with more than just "points".

Have a healthy 1999.
0

Author Commented:
Whoops...

I just thought of a related question...

In my test example above, I created an array of Integer, containing a max of 20 items:

var
TheArray : Array[1..20] of integer;

But it later occurred to me that in my particular case, I could have up to a max of 1000, but I am afraid of declaring an array so large (using Delphi 1, limited stack space?).  I will know during runtime the max number that the user wishes to choose, but I don't know this max number at compile time.  How can I efficiently handle this situation?  Can I declare an array of Integer dynamically at run time? I.e., with a variable upper bounds?  E.g.,

var
TheArray : Array[1..max] of integer;
0

Commented:
Try this version of it - it will allow you to set the upper and lower bounds of the array regardless of what you initialize it as:

procedure CompRandArray(var ArrayToFill: Array of Integer; LowBounds, HighBounds, LowRange, HighRange: Integer);
var
I, J: integer;
HaveDup: boolean;
begin
Randomize;
if (HighRange + 1 - LowRange) < ((HighBounds + 1) - LowBounds) then
Raise ERangeError.Create('Range to small to fill given Array');
if (LowBounds < Low(ArrayToFill)) or (HighBounds > High(ArrayToFill)) then
Raise ERangeError.Create('Bounds dont fit within Array Range');
for I := LowBounds to HighBounds do
begin
Sleep(0);
Repeat
ArrayToFill[I] := Random(HighRange + 1);
Until ArrayToFill[I] >= LowRange;
Repeat
HaveDup := False;
for J := LowBounds to HighBounds do
begin
Sleep(0);
if (ArrayToFill[J] = ArrayToFill[I]) and (I <> J) then
begin
Repeat
ArrayToFill[I] := Random(HighRange + 1);
Until ArrayToFill[I] >= LowRange;
HaveDup := True;
break;
end;
end;
Until HaveDup = False;
end;
end;

1. Make Sure HighBounds and LowBounds fall within range of given Array.  The Array can be as large as need and you can change the bounds to whatever you want when you call the function.

2. Odd problem.  In Delphi 3 anyway, when Array is a global variable and (HighRange - LowRange) = (HighBounds - LowBounds), the results are always the same.  This does not happen if Array is declared locally.  My guess is Random function somehow relies on the stack condition when it is called.  As long as above condition is false it works fine though.

Hope this helps

0

Author Commented:
Thanks, but something is wrong.  Using the code below, I will always get "0" as the first element in the returned array, when the range was defined from 1 to 22.  IOW, RandomArray[1] will come back with a value of 0.

var
Form1: TForm1;
RandomArray : Array[1..40] of Integer;

procedure CompRandArray(var ArrayToFill: Array of Integer; LowBounds, HighBounds, LowRange, HighRange: Integer);

implementation

{\$R *.DFM}

procedure TForm1.Button1Click(Sender: TObject);
var
Ctr : Integer;
begin
CompRandArray(RandomArray, 1, 22,1,22);
Memo1.Clear;
For Ctr := Low(RandomArray) to High(RandomArray) do begin
end;
end;

Also, to complicate things more, your code, although it addressed a particular issue that I originally overlooked, still doesn't address the issue of a dynamic array declaration.
0

Commented:
I will re-write function momentarily to address dynamic array problem - (I have an idea :) ) but the bug you are having is not in the function - it is in your Button Click code

This is not right:
...
For Ctr := Low(RandomArray) to High(RandomArray) do begin
...

it should be

...
For Ctr := 1 to 22 do begin
...

since you altered the bounds of the Array, but maybe my implementation is poor for your purposes - re-writing a different way now.
0

Commented:
Here you go this should work much better for you

Changes made - Array now dynamic - You should declare locally as I will give example.  Implemented some code optimizations as suggested by VictorNet.  No more bug if (HighRange - LowRange) = (HighBounds - LowBounds). Just include following unit in your fom code

unit RandomArray;

interface

uses Windows;

type
TIntegerArray = array[0..32760] of Integer;
PIntegerArray = ^TIntegerArray;

function CompRandArray(var IntArrayPtr: PIntegerArray; Count, LowRange, HighRange: integer): boolean;

implementation

function CompRandArray(var IntArrayPtr: PIntegerArray; Count, LowRange, HighRange: integer): boolean;
var
I, J: integer;
HaveDup: boolean;
begin
Result := True;
if (HighRange - LowRange + 1) < (Count) then
begin
Result := False;
Exit;
end;
Randomize;
for I := 0 to Count - 1 do
begin
Sleep(0);
IntArrayPtr^[I] := LowRange + Random(HighRange - LowRange + 1);
Repeat
HaveDup := False;
for J := 0 to I - 1 do
begin
Sleep(0);
if (IntArrayPtr^[J] = IntArrayPtr^[I]) and (I <> J) then
begin
IntArrayPtr^[I] := LowRange + Random(HighRange - LowRange + 1);
HaveDup := True;
break;
end;
end;
Until HaveDup = False;
end;
end;

end.

This is example of how to call this properly

procedure TForm1.Button1Click(Sender: TObject);
var
RandomArray: PIntegerArray; //This is a pointer type to Dynamic array
Ctr, Count, Low, High: integer;
begin
Count := 20; //fill with 20 items
Low := 0; //Lowest Random Number
High := 19; //Highest Random Number
GetMem(RandomArray, Count*SizeOf(Integer)); //Allocate memory
try
ListBox1.Clear;
if CompRandArray(RandomArray, Count, Low, High) then
For Ctr := 0 to Count - 1 do
ListBox1.Items.Add(IntToStr(RandomArray^[Ctr])); //dont forget ^
//if false Something went wrong
finally
FreeMem(RandomArray, Count*SizeOf(Integer)); //DeAllocate
end;
end;

Hope this works better.
0

Author Commented:
>> Hope this works better.

Much, much better!  I have my application up and running with the new function, and so far things seem to be working great.

You have gone above and beyond the call of duty.

Thanks!
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.