how would you generate random integers that are unique from each other in pascal

delphi, integer, random

Solution

I would do it like this:

- Put the numbers 1 to 49 into an array.

- Perform a shuffle on the array.

- Pull out the first 6 elements.

It's probably not the most efficient way, but it's easy to implement, easy to understand, and, most crucially, easy to reason about the distributional properties of your sampling method.

For the shuffle, use Fisher-Yates shuffle. I implement that like this, in a generic method:

procedure TRandomNumberGenerator.Permute<T>(var Values: array of T);
var
  i, Count: Integer;
begin
  Count := Length(Values);
  for i := 0 to Count-2 do
    TGeneric.Swap<T>(Values[i], Values[i + Uniform(Count-i)]);
end;

where `Uniform(N)` is the function of my RNG that returns a value drawn from the uniform distribution over `0..N-1`. You could replace that with `Random` in your code. And `TGeneric.Swap<T>` swaps the two elements.

You could modify this to work on an array of integers like so:

procedure Swap(var lhs, rhs: Integer);
var
  tmp: Integer;
begin
  tmp := lhs;
  lhs := rhs;
  rhs := tmp;
end;

procedure Permute(var Values: array of Integer);
var
  i, Count: Integer;
begin
  Count := Length(Values);
  for i := 0 to Count-2 do
    Swap(Values[i], Values[i + Random(Count-i)]);
end;

Of course, you only need to perform the first six iterations of the loop, so a very efficient version would be like this:

function Choose(M, N: Integer): TArray<Integer>;
var
  i: Integer;
  Values: TArray<Integer>;
begin
  Assert(M>0);
  Assert(N>=M);

  SetLength(Values, N);
  for i := 0 to N-1 do
    Values[i] := i+1;

  for i := 0 to Min(M-1, N-2) do
    Swap(Values[i], Values[i + Random(N-i)]);

  Result := Copy(Values, 0, M);
end;

You would call this passing 6 and 49:

Values := Choose(6, 49);

If you were a mad performance freak then I think it would be hard to beat this:

type
  TArr6 = array [0..5] of Integer;
  PArr6 = ^TArr6;
  TArr49 = array [0..48] of Integer;

const
  OrderedArr49: TArr49 = (
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
    19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
    35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49
  );

function Choose6: TArr6;
var
  i: Integer;
  Values: TArr49;
begin
  Values := OrderedArr49;
  for i := 0 to high(Result) do begin
    Swap(Values[i], Values[i + Random(Length(Values)-i)]);
  end;
  Result := PArr6(@Values)^;
end;

I should say that I doubt that performance would be the driving factor here.

Problem

Original source