Recent

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

Bart

  • Hero Member
  • *****
  • Posts: 5275
    • Bart en Mariska's Webstek
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: 2330
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: 4144
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 »

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
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;
  59.   readln;
  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 »
Specialize a type, not a var.

Eugene Loza

  • Hero Member
  • *****
  • Posts: 663
    • My games in Pascal
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.
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
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;
  18.   readln;
  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 »
Specialize a type, not a var.

Eugene Loza

  • Hero Member
  • *****
  • Posts: 663
    • My games in Pascal
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!
My FOSS games in FreePascal&CastleGameEngine: https://decoherence.itch.io/ (Sources: https://gitlab.com/EugeneLoza)

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
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.
[edit] 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 »
Specialize a type, not a var.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: How to efficiently generate a list of random integers within a range?
« Reply #11 on: April 10, 2017, 09:40:51 am »
[edit] 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. :)

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
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 »
Specialize a type, not a var.

Zoran

  • Hero Member
  • *****
  • Posts: 1829
    • http://wiki.lazarus.freepascal.org/User:Zoran
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. :)

Thaddy

  • Hero Member
  • *****
  • Posts: 14201
  • Probably until I exterminate Putin.
Re: How to efficiently generate a list of random integers within a range?
« Reply #14 on: April 10, 2017, 01:17:17 pm »
"Decrement max by 1 and continue. When max is 0, set max back to the size of the array - 1"
Is the wrong  order. element zero will never be processed... N=1000... as the comments tell you.
Specialize a type, not a var.

 

TinyPortal © 2005-2018