Random ?

[J-G]

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.

[Fibonacci]

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]

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 

Thanks Fibonacci!  -  though with a 'handle' like that maybe it should have been expected 

[Fibonacci]

You're welcome =)

[alpine]

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)

[Bart]

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]

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...

[Thaddy]

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.

[Zoran]

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.

[Thaddy]

Yes, not always. But it is fun. 
The difference is negligable, though, so I chose the xor swap because I like it.
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.