Solved

Making a unique random list of numbers

Posted on 1998-12-31
21
491 Views
Last Modified: 2010-04-04
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?
0
Comment
Question by:Monroe406
  • 9
  • 5
  • 5
  • +1
21 Comments
 
LVL 5

Accepted Solution

by:
heathprovost earned 150 total points
ID: 1354025
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
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354026
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 Comment

by:Monroe406
ID: 1354027
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).
0
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354028
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
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354029
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
 
LVL 27

Expert Comment

by:kretzschmar
ID: 1354030
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
0
 
LVL 10

Expert Comment

by:viktornet
ID: 1354031
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
 
LVL 10

Expert Comment

by:viktornet
ID: 1354032
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
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354033
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
 
LVL 10

Expert Comment

by:viktornet
ID: 1354034
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 10

Expert Comment

by:viktornet
ID: 1354035
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
 
LVL 27

Expert Comment

by:kretzschmar
ID: 1354036
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
0
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354037
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
 
LVL 10

Expert Comment

by:viktornet
ID: 1354038
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 Comment

by:Monroe406
ID: 1354039
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 Comment

by:Monroe406
ID: 1354040
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
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354041
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

0
 

Author Comment

by:Monroe406
ID: 1354042
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.
0
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354043
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.
0
 
LVL 5

Expert Comment

by:heathprovost
ID: 1354044
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 Comment

by:Monroe406
ID: 1354045
>> 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

Featured Post

What Is Threat Intelligence?

Threat intelligence is often discussed, but rarely understood. Starting with a precise definition, along with clear business goals, is essential.

Join & Write a Comment

The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
In my programming career I have only very rarely run into situations where operator overloading would be of any use in my work.  Normally those situations involved math with either overly large numbers (hundreds of thousands of digits or accuracy re…
This video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …
This video explains how to create simple products associated to Magento configurable product and offers fast way of their generation with Store Manager for Magento tool.

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

16 Experts available now in Live!

Get 1:1 Help Now