Link to home
Start Free TrialLog in
Avatar of Monroe406
Monroe406

asked on

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?
ASKER CERTIFIED SOLUTION
Avatar of heathprovost
heathprovost
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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;

Avatar of Monroe406
Monroe406

ASKER

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
            Memo1.Lines.Add(IntToStr(RandomArray[Ctr]));
      end;
end;


Here I am trying to choose 20 random numbers out of a total of 20 (e.g., 1-20).
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;
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.
Avatar of kretzschmar
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
    Listbox1.Items.add(inttostr(TheArray[i]));
end;


meikl
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
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
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!
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
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
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
  s := SToPad;
  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
    Listbox1.Items.add(PadRight(inttostr(MyArray[i]),Length(Edit1.text)));
end;




end.

meikl
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 :)
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
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.
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;
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;

Comments:

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

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
            Memo1.Lines.Add(IntToStr(RandomArray[Ctr]));
      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.
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
Memo1.Lines.Add(IntToStr(RandomArray[Ctr]));
...

it should be

...
For Ctr := 1 to 22 do begin
ListBox1.Items.Add(IntToStr(RandomArray[Ctr]));
...

since you altered the bounds of the Array, but maybe my implementation is poor for your purposes - re-writing a different way now.
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.
>> 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!