Recent

Author Topic: Random ?  (Read 3735 times)

J-G

  • Hero Member
  • *****
  • Posts: 958
Random ?
« on: August 21, 2023, 03:56:41 pm »
It's a while since I last did any programming and I don't recall ever needing a set of random numbers so I'm somewhat struggling to determine whether I can - quickly and easily - create a complete set of unique random numbers in the range 1 to 16 (inclusive).

I have found Random Range and can create a random number in that range and I've even used Randomize to see whether a second call creates a different number. What I'm looking for is a routine which will (simply) return a list of 16 unique numbers - or rather if it is possible to achieve this easily without having to recurse and check that the number hasn't already been selected.

Thanks.
FPC 3.0.0 - Lazarus 1.6 &
FPC 3.2.2  - Lazarus 2.2.0 
Win 7 Ult 64

Fibonacci

  • Hero Member
  • *****
  • Posts: 649
  • Internal Error Hunter
Re: Random ?
« Reply #1 on: August 21, 2023, 04:08:43 pm »
Code: Pascal  [Select][+][-]
  1. var
  2.   rands: array[1..16] of integer;
  3.   i, r, t: integer;
  4.  
  5. begin
  6.   //call once
  7.   randomize;
  8.  
  9.   //fill
  10.   for i := low(rands) to high(rands) do rands[i] := i;
  11.  
  12.   //shuffle
  13.   for i := low(rands) to high(rands) do begin
  14.     //random index
  15.     r := low(rands)+random(high(rands));
  16.     //store in temp var
  17.     t := rands[i];
  18.     //replace
  19.     rands[i] := rands[r];
  20.     //restore temp
  21.     rands[r] := t;
  22.   end;
  23.  
  24.   //output
  25.   for i := low(rands) to high(rands) do write(rands[i], ' ');
  26.  
  27.   readln;
  28. end.

5 2 1 12 3 13 16 7 4 8 9 10 15 14 6 11

J-G

  • Hero Member
  • *****
  • Posts: 958
Re: Random ?
« Reply #2 on: August 21, 2023, 04:35:33 pm »

5 2 1 12 3 13 16 7 4 8 9 10 15 14 6 11
Fantastic!  - in just a smidgeon over 12 minutes EXACTLY what I thought was going to take me at least a day  :D

Thanks Fibonacci!  -  though with a 'handle' like that maybe it should have been expected  :D
FPC 3.0.0 - Lazarus 1.6 &
FPC 3.2.2  - Lazarus 2.2.0 
Win 7 Ult 64

Fibonacci

  • Hero Member
  • *****
  • Posts: 649
  • Internal Error Hunter
Re: Random ?
« Reply #3 on: August 21, 2023, 04:44:40 pm »
You're welcome =)

alpine

  • Hero Member
  • *****
  • Posts: 1343
Re: Random ?
« Reply #4 on: August 21, 2023, 05:05:17 pm »
Just a bit of refinement:
Code: Pascal  [Select][+][-]
  1.   ...
  2.   //shuffle
  3.   for i := low(rands) to high(rands)-1 do begin
  4.     //random index
  5.     r := i+random(high(rands)+1-i);
  6.     ...
(Fisher-Yates)
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

Bart

  • Hero Member
  • *****
  • Posts: 5509
    • Bart en Mariska's Webstek
Re: Random ?
« Reply #5 on: August 21, 2023, 06:00:19 pm »
From my ExtMath unit:
Code: Pascal  [Select][+][-]
  1. function RandomArray(aFrom, aTo, aSize: Integer): TIntegerDynArray; overload;
  2. function RandomArray(aFrom, aTo: Integer): TIntegerDynArray; overload;
  3. function RandomArray(Range: Integer): TIntegerDynArray; overload;
  4. function RandomArray(aFrom, aTo, aSize: Int64): TInt64DynArray; overload;
  5. function RandomArray(aFrom, aTo: Int64): TInt64DynArray; overload;
  6. function RandomArray(Range: Int64): TInt64DynArray; overload
All use Sattolo algorithm for shuffling.

Bart

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #6 on: August 21, 2023, 06:10:17 pm »
Note I did a write up on the wiki and also on Rosetta code a couple of years ago.
There was even a slight discussion about Fisher-Yates and Sattolo on this forum.
The code on Rosetta Code is correct and Bart probably used that.
Note too that I had to correct a wrong edit... >:D
But I am sure they don't want the Trumps back...

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #7 on: January 13, 2025, 12:56:14 pm »
Been some time but,
I replaced my Rosetta code entry altogether and added this:
Code: Pascal  [Select][+][-]
  1. program sattologeneric;
  2. {$mode objfpc}{$modeswitch implicitfunctionspecialization}
  3.  
  4. generic procedure SattoloCycle<T>(var arr: array of T);
  5. var
  6.  i,j:integer;
  7.  temp:T;
  8. begin
  9.   for i := High(arr) downto 1 do
  10.   begin
  11.     j := Random(i);
  12.     temp  := arr[i]; // can't
  13.     arr[i] := arr[j];// use
  14.     arr[j] := temp;  // xor
  15.   end;
  16. end;
  17.  
  18. var
  19.   a:Array of byte = (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19);
  20.   c:integer;
  21. begin
  22.   Randomize;
  23.   SattoloCycle(a);
  24.   for c in a do write(c:3);
  25. end.
Which is strictly only trunk and this:
Code: Pascal  [Select][+][-]
  1. program sattolo;
  2.  
  3. procedure SattoloCycle(var arr: array of integer);
  4. var
  5.  i,j:integer;
  6. begin
  7.   for i := High(arr) downto 1 do
  8.   begin
  9.     j := Random(i);
  10.     arr[i] := arr[i] xor arr[j];// swap
  11.     arr[j] := arr[j] xor arr[i];// without
  12.     arr[i] := arr[i] xor arr[j];// temp
  13.   end;
  14. end;
  15.  
  16. var
  17.   a:Array of integer = (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19);
  18.   c:integer;
  19. begin
  20.   Randomize;
  21.   SattoloCycle(a);
  22.   for c in a do write(c:3);
  23. end.
for the backwards compatibility with 3.2.0.

Any comments?
( I would love to submit it as a utility function in sysutils )

Both versions are faster than the other answers and I can not see any room for improvement.
« Last Edit: January 13, 2025, 05:55:07 pm by Thaddy »
But I am sure they don't want the Trumps back...

Zoran

  • Hero Member
  • *****
  • Posts: 1899
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Random ?
« Reply #8 on: January 13, 2025, 06:12:53 pm »

Any comments?
( I would love to submit it as a utility function in sysutils )

Both versions are faster than the other answers and I can not see any room for improvement.


Only that swap using auxiliary variable is faster than xor-swap. perhaps not always, though.
Swan, ZX Spectrum emulator https://github.com/zoran-vucenovic/swan

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #9 on: January 13, 2025, 07:26:20 pm »
Yes, not always. But it is fun.  :D
The difference is negligable, though, so I chose the xor swap because I like it. :D
The generic version uses a temp, because you can't assume T is an ordinal.

The swap way is mostly intel/amd issue, e.g. arm has very fast xor.
« Last Edit: January 14, 2025, 11:45:10 am by Thaddy »
But I am sure they don't want the Trumps back...

Zoran

  • Hero Member
  • *****
  • Posts: 1899
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Random ?
« Reply #10 on: January 20, 2025, 11:33:07 am »
Thaddy, shouldn't it be
Code: Pascal  [Select][+][-]
  1.   j := Random(i + 1);
instead of
Code: Pascal  [Select][+][-]
  1.   j := Random(i);

The random permutation should allow the possibility that an element stays where it had been, shouldn't it?

Your example can never leave 19 at the final position.

Also note that if the function is changed as I suggest, the fun with xor is over -- you must not use xor-swap, as it fails when used on the same variable. Of course, you can keep xor-swap, provided you add the condition if j<>i and only then perform the swap.
Swan, ZX Spectrum emulator https://github.com/zoran-vucenovic/swan

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #11 on: January 20, 2025, 11:44:28 am »
No, random(i). that is because sattolo's last swap is swap(i) with swap(i+1)...
Or when applied in reverse, of course the reverse.
Otherwise the algorithm becomes Knuth's - which is Fisher-Yates - version and not all members always change position: it then becomes possibe that a member is in the same position from the start of the shuffle.
That was also the major mistake that the one who editted my first version on Rosetta code made. It is a common error. You have to understand that the upper i is not inclusive.
If it were inclusive we needed to iterate for i-1....
A good explanation is here:
https://danluu.com/sattolo/

Were you the vandal that tried to mutilate my first version?  >:(

My implementation is absolutely correct.
« Last Edit: January 20, 2025, 11:47:32 am by Thaddy »
But I am sure they don't want the Trumps back...

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #12 on: January 20, 2025, 11:49:33 am »
Your example can never leave 19 at the final position.
That is the essense of Sattolo's algorithm. No member can end-up in the same position....
Inclined to use some devils here.....

You still don't get it, do you?

If the above link did not help try this:
https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Basically in Sattolo every swap has exactly one cycle, so it is guaranteed that every member has a different position from where it started.
So 19 can never be at 19. That is the whole point.
« Last Edit: January 20, 2025, 11:58:53 am by Thaddy »
But I am sure they don't want the Trumps back...

Zoran

  • Hero Member
  • *****
  • Posts: 1899
    • http://wiki.lazarus.freepascal.org/User:Zoran
Re: Random ?
« Reply #13 on: January 20, 2025, 11:56:09 am »
Your example can never leave 19 at the final position.
That is the essense of Sattolo's algorithm. No member can end-up in the same position....
Inclined to use some devils here.....

That is exactly what your code does, it excludes the permutations where any element remains at it position.
It might be what Sattolo is, but it surely is not what is asked for it this thread. Random permutations must include all permutations.
Swan, ZX Spectrum emulator https://github.com/zoran-vucenovic/swan

Thaddy

  • Hero Member
  • *****
  • Posts: 16520
  • Kallstadt seems a good place to evict Trump to.
Re: Random ?
« Reply #14 on: January 20, 2025, 12:02:35 pm »
Quote
or rather if it is possible to achieve this easily without having to recurse and check that the number hasn't already been selected.
Implies Sattolo, because otherwise you would need a flag of some sort for every member. Did you miss that?

Btw, if you want Knuth, you can do it like this:
Code: Pascal  [Select][+][-]
  1. program randomsort;
  2. {$ifdef fpc}{$mode objfpc}{$H+}{$endif}
  3. uses classes;
  4.  
  5. function Rsort(l:TStringList;a,b:integer):integer;
  6. begin
  7.   { becomes -1, 0 or 1 }
  8.   result := Random(3)-1;
  9. end;
  10. var
  11.   list:TStringList;
  12. begin
  13.   list := TStringList.create;
  14.   list.add('test1');
  15.   list.add('test2');
  16.   list.add('test3');
  17.   list.add('test4');
  18.   list.add('test5');
  19.   list.add('test6');
  20.   list.add('test7');
  21.   list.add('test8');
  22.   list.add('test9');
  23.   list.add('test0');
  24.   list.add('test0');
  25.   list.add('test19');  // on request
  26.   randomize;
  27.   list.CustomSort(@Rsort);
  28.   Writeln(list.text);
  29.   list.free;
  30. end.
Where 19 can end up 19  :D ;) :) 8)
This is the simplest way to random sort without duplicates.
Solves your issue because members can end up in the same place.
« Last Edit: January 20, 2025, 12:17:33 pm by Thaddy »
But I am sure they don't want the Trumps back...

 

TinyPortal © 2005-2018