Author: Jonas Bilinkevicius

How can I write a procedure that does not choose the same number more than once?

Answer:

This is called "shuffling". Most often, you want it to randomize the values in a 
list or array. In any case, the only way to count "more than once" is to do this 
over a given array. If you just want the shuffle values one by one, you shuffle the 
array and then take the values from the lowest element to the highest, successively.

The thing to avoid is to go and keep a list of the numbers already found, and call 
random endlessly until it gives a number not on the list. With a large range, this 
takes incredibly long.

The procedure below shows how to do it correctly. It assumes you want a continuous 
range of values. If you want something fancier (say, a shuffle of various weights, 
or of names, etc.), then you merely have to change the procedure to take an array 
of the proper type, and NOT to fill it at the beginning - the caller can pre-fill 
it with the values wanted.
1   
2   procedure shuffle(var a: array of integer; nLow: integer);
3   {"a" holds all values from nLow to nLow + high(a) in pseudorandom order.
4   Method: Fill array with values in order. Values above jTop are shuffled. jTop 
5   starts at array top and moves down one element per step. We're done when jTop is 
6   a[0]. On each step, a random element below jTop is exchanged with the one at jTop}
7   var
8     j: integer;
9     jTop: integer;
10    nTemp: integer;
11  begin
12    for j := 0 to high(a) do
13      a[j] := j + nLow;
14    jTop := high(a);
15    randomize;
16    while (jTop > 0) do
17    begin
18      j := random(jTop + 1);
19      nTemp := a[j];
20      a[j] := a[jTop];
21      a[jTop] := nTemp;
22      dec(jTop);
23    end;
24  end;