### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: How to efficiently generate a list of random integers within a range?  (Read 13719 times)

#### Bart

• Hero Member
• Posts: 4096
##### How to efficiently generate a list of random integers within a range?
« on: April 08, 2017, 07:47:38 pm »
I want to generate a list (array?) of NRequired random integers that range from 0 to Max (both inclusive). NReq is not known at compile time.
The list may not contain duplicate entries.
Is there a more efficient way of doing it like this (pseudocode):

Code: [Select]
`  0. N := 0;  1. NewValue := RandomRange(0, Max+1)  2. Loop through each value in the list: is it the same as NewValue?  3. If so, then repeat 1..2 until you come up with a value that is not in the array yet  4. Add NewValue to array  5. Inc(N)  6. If (N = NRequired) then STOP`
I don't care what structure is used for the list.

Bart

#### molly

• Hero Member
• Posts: 2345
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #1 on: April 08, 2017, 08:04:54 pm »
It was discussed on this forums a while ago as well, but have a look at this SO Question or this blogpost.

So, it can be done more efficiently as shown in your example.

#### howardpc

• Hero Member
• Posts: 3608
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #2 on: April 08, 2017, 11:23:46 pm »
I doubt that this is the most efficient algorithm, but it is pretty efficient.

Code: Pascal  [Select][+][-]
1. uses
2.   math;
3.
4. type TIntArray = array of integer;
5.
6.   function RandomArray(aMaxValue, aRequiredCount: integer): TIntArray;
7.   var
8.     usedArr: TIntArray;
9.     maxVal, i: integer;
10.
11.     function GetUniqueRandom: integer;
12.     begin
13.       repeat
14.         Result:=RandomRange(0, maxVal);
15.       until (usedArr[Result] = 0);
16.     end;
17.
18.   begin
19.     Assert(aRequiredCount<aMaxValue,'RandomArray: impossible requirement');
20.     Randomize;
21.     maxVal:=aMaxValue+1;
22.     SetLength(usedArr, maxVal);
23.     SetLength(Result, aRequiredCount);
24.     for i:=0 to High(Result) do begin
25.       Result[i]:=GetUniqueRandom;
26.       Inc(usedArr[Result[i]]);
27.     end;
28.   end;

« Last Edit: April 08, 2017, 11:34:42 pm by howardpc »

• Hero Member
• Posts: 10683
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #3 on: April 09, 2017, 09:25:31 am »
Here's a class translated from https://github.com/preshing/RandomSequence/blob/master/randomsequence.h
It seems actually pretty good, provided you know it doesn't really pass any serious random tests. It merely fools you.
But it looks random and is unique It's also faster than a linked lists + swap and remove
Code: Pascal  [Select][+][-]
1. program uniquerand32;
2. {\$mode objfpc}
3. type
4.
5.   { UniqueRandom32 }
6.   UniqueRandom32 = class sealed
7.   private
8.       class var m_index:cardinal;
9.       class var m_intermediateOffset:Cardinal;
10.       class var Fseedbase,Fseedoffset:Cardinal;
11.       class function permuteQPR(x:cardinal):cardinal;static;inline;
12.   public
13.       class constructor UniqueRandom32;
14.       class function Next:Cardinal;inline;static;
15.     end;
16.
17. class function UniqueRandom32.permuteQPR(x: cardinal): cardinal;
18. const
19.    prime:Cardinal = 4294967291;// closest prime to High(Cardinal);
20.    Residue:Cardinal = 0;
21. begin
22.   if x >= prime then
23.     Result := x
24.   else // The 5 integers out of range are mapped to themselves.
25.     begin
26.       residue := (qword(x) * x) mod prime;
27.       if x <= (prime div 2) then
28.         result:= residue
29.       else
30.         result := prime - residue;
31.     end;
32. end;
33.
34. class constructor UniqueRandom32.UniqueRandom32;
35. begin
36.   FSeedBase :=RandSeed;
37.   FSeedOffset := not Randseed;
38.   m_index := permuteQPR(permuteQPR(FseedBase) + \$682f0161);
39.   m_intermediateOffset := permuteQPR(permuteQPR(FseedOffset) + \$46790905);
40. end;
41.
42. class function UniqueRandom32.Next: Cardinal;
43. begin
44.   Result := permuteQPR((permuteQPR(m_index) + m_intermediateOffset) xor \$5bf03635);
45.   inc(m_index);
46. end;
47.
48. { demo }
49. var
50.   i:integer;
51. begin
52.   randseed := 5469;  // must seed
53.   //randomize;       // or randomize
54.   for i := 1 to 100 do
55.   begin
56.     write(UniqueRandom32.Next:20);
57.     if i mod 5 = 0 then writeln;
58.   end;
60. end.

Note that if you do any math scaling, you will loose that uniqueness, though, so it may not be suitable for Bart without further work.
Quick tested with a TList<Cardinal> from rtl-generics, List.sort and   Assert(List.IndexOf(List[i-1]) = List.LastIndexOf(List[i-1]),'Has duplicates'); over 3.000.000 entries: no duplicates as expected.
« Last Edit: April 09, 2017, 10:55:49 am by Thaddy »

#### Eugene Loza

• Hero Member
• Posts: 570
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #4 on: April 09, 2017, 11:12:13 am »
I've never did it that way, but shuffling looks efficient when the amount of numbers one needs to get is high:
Code: Pascal  [Select][+][-]
1. var A: array of integer;
2. i,j: integer;
3. ...
4. setlength(A,max_random_number);
5. //fill the array
6. for i := 0 to max_random_number do A[i] := i;
7. //shuffle the array (double inefficiency)
8. for i := 0 to how_many_random_numbers_needed do begin
9.   j := random(max_random_number)
10.   tmp := A[i];
11.   A[i] := A[j];
12.   A[j] := tmp;
13. end;
14. //and get the numbers
15. for i := 0 to how_many_random_numbers_needed do
16.   some_result := A[i];
17.
Might also be done with generic lists, etc.

However, pay attention, most of the methods are CPU-efficient, but RAM-inefficient.
Lazarus 1.9 + FPC 3.1.1 Debian Jessie 64 bit.

My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)
Sources are here: https://github.com/eugeneloza?tab=repositories

• Hero Member
• Posts: 10683
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #5 on: April 09, 2017, 08:05:54 pm »
I have a version of my above code that stores m_index at hi(qword) and the random at lo(qword) in one go.
When  the number of required randoms are stored in a list or array and sorted on random, the m_index value becomes a unique random for the range.
The result is a very fast random - because the random sequence is pre-calculated - after initial setup and sort at the cost of memory for the list. If this is acceptable for Bart I can put it here as well.

I also did some tests on the randomness for the original code with diehard. It's pretty good for its purpose.
Note it is more or less an LCG and the uniqueness comes from its modulo (superhigh prime). Other LCG's can do the same or massaged to do the same given a high prime for a 32 bits  unsigned. An LCG will never repeat itself for values: 0 < random < prime unless you perform an extra operation like a multiplication. (e.g 2 x 6 = 3 x 4 = 1 x 12 etc)
« Last Edit: April 09, 2017, 08:15:00 pm by Thaddy »

• Hero Member
• Posts: 10683
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #6 on: April 10, 2017, 08:11:43 am »
You may also like Sattolo's algorithm, which goes like this:
Code: Pascal  [Select][+][-]
1. program sattolocycle;
2. {\$mode delphi}
3. uses math;
4. var
5.   a:Array of cardinal;
6.   i,j:integer;
7.   t:cardinal;
8. begin
9.   a:=a.Create(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19);
10.   i := length(a);
11.   while i > 0 do
12.   begin
13.     dec(i);
14.     j :=randomrange(Low(a),i);
15.     t:=a[i];a[i]:=a[j];a[j]:=t;
16.     writeln(a[i]);
17.   end;
19. end.
20.

This is close to what Eugene wrote but here the random range decreases. It is the most efficient I found yet for defined number ranges other that full cardinal.
See: https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Sattolo.27s_algorithm
« Last Edit: April 10, 2017, 08:28:48 am by Thaddy »

#### Eugene Loza

• Hero Member
• Posts: 570
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #7 on: April 10, 2017, 08:30:22 am »
Thaddy, wow, that's fantastic!!! I knew there should have been a more efficient way to!
Lazarus 1.9 + FPC 3.1.1 Debian Jessie 64 bit.

My Free and Open Source games in Lazarus/FreePascal/CastleGameEngine:
https://decoherence.itch.io/
(and some ancient games in Turbo Pascal too)
Sources are here: https://github.com/eugeneloza?tab=repositories

#### Zoran

• Hero Member
• Posts: 1642
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #8 on: April 10, 2017, 08:54:00 am »
Thaddy, wow, that's fantastic!!! I knew there should have been a more efficient way to!

Actually, Molly gave the link to stackoverflow page with this solution in the first reply in this topic. See it, as it is very well explained there.

• Hero Member
• Posts: 10683
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #9 on: April 10, 2017, 09:02:16 am »
When you google you will often find the same sources. Note that I found a direct link to the C++ sourcecode for the class that I translated. But indeed, after a few clicks on molly's links you finally arrive at the same spot.

And that reaction by Eugene was about the sattoro code, which is different from Molly's links.
 Ah I see, Molly links to Fisher Yates. Sattoro is not Fisher Yates...It is an improvement on Fisher Yates (just one cycle) . Same answer:independent.
« Last Edit: April 10, 2017, 09:32:17 am by Thaddy »

#### Zoran

• Hero Member
• Posts: 1642
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #10 on: April 10, 2017, 09:34:26 am »
When you google you will often find the same sources. Note that I found a direct link to the C++ sourcecode for the class that I translated. But indeed, after a few clicks on molly's links you finally arrive at the same spot.

And that reaction by Eugene was about the sattoro code, which is different from Molly's links.

Isn't this sattoro code same as the chosen solution in molly's link

I just wanted to point Eugene to that link, because it has a very nice and easy-to-understand explanation.
« Last Edit: April 10, 2017, 09:36:35 am by Zoran »

#### Zoran

• Hero Member
• Posts: 1642
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #11 on: April 10, 2017, 09:40:51 am »
 Ah I see, Molly links to Fisher Yates. Sattoro is not Fisher Yates...It is an improvement on Fisher Yates (just one cycle) . Same answer:independent.

I think that this link explains just that algorithm - Sattoro, just doesn't call it so, but says it's modified Fisher Yates.

Edit: I didn't check myself what Sattoro is and what Fisher-Yates is, but the explained algorithm is just what you posted.

• Hero Member
• Posts: 10683
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #12 on: April 10, 2017, 09:43:40 am »
No, that answer on stackoverflow is a naive implementation of the same (Sattoro) optimization if I read it correctly.
He actually initializes a whole array for the range needed + 1. (1001)
Thus it wastes space for one element.
Sattoro uses space exactly as is needed. (1000)

So, yes, he came up with a solution that in effect is like Sattoro's, but his implementation is not optimal (one may say wrong, but that doesn't do him justice).
My implementation is EXACT Sattoro and allocates space for the EXACT number of elements.

Note Sattoro is indeed a modified Fisher-Yates.
« Last Edit: April 10, 2017, 09:49:39 am by Thaddy »

#### Zoran

• Hero Member
• Posts: 1642
##### Re: How to efficiently generate a list of random integers within a range?
« Reply #13 on: April 10, 2017, 09:51:54 am »
No, that answer on stackoverflow is a naive implementation of the same (Sattoro) optimization if I read it correctly.
He actually initializes a whole array for the range needed + 1. (1001)
Thus it wastes space for one element.
Sattoro uses space exactly as is needed. (1000)

So, yes, he came up with a solution that in effect is like Sattoro's, but his implementation is not optimal (one may say wrong, but that doesn't do him justice).
My implementation is EXACT Sattoro and allocates space for the EXACT number of elements.

You allocate 20 numbers for range 0..19, he allocates 1001 for range 0..1000.
For wanted range 0..n, both of you allocate n + 1 numbers.