Mirror

How to use Randomize so that the same value is not chosen more than once (Views: 100)


Problem/Question/Abstract:

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.

procedure shuffle(var a: array of integer; nLow: integer);
{"a" holds all values from nLow to nLow + high(a) in pseudorandom order.
Method: Fill array with values in order. Values above jTop are shuffled. jTop starts at array top and moves down one element per step. We're done when jTop is a[0]. On each step, a random element below jTop is exchanged with the one at jTop}
var
  j: integer;
  jTop: integer;
  nTemp: integer;
begin
  for j := 0 to high(a) do
    a[j] := j + nLow;
  jTop := high(a);
  randomize;
  while (jTop > 0) do
  begin
    j := random(jTop + 1);
    nTemp := a[j];
    a[j] := a[jTop];
    a[jTop] := nTemp;
    dec(jTop);
  end;
end;

<< Back to main page