如何在Pascal中生成不重复的随机整数

Question

我希望能够用Pascal编写一个程序，从1到49之间随机选择6个不同的整数。这里的“不同”的意思是：不能出现像“8,22,22,32,37,43”这样的情况，因为数字“22”重复了。您能告诉我如何在Delphi中实现吗？

如果用以下代码，可以得到1到49之间的6个随机数。

for i := 1 to 6 do
  begin 
    num[i] := random(49) + 1
  end
{next};

- ProtectorOfUbi

---

一种非常简单的方法是先将数字0到max-1填充到一个列表中，然后使用random(count(list))随机选择并删除一个数字。 - 500 - Internal Server Error

那么，我的表达方式更像是Pascal语言的，而不是你的 ;) - 500 - Internal Server Error

听起来像是一个彩票号码生成器 :) - Jerry Dodge

我很难理解为什么上面的代码不是他想要的。 - Nick Hodges

@NickHodges 因为同一个数字可能会出现多次的机会。 - Jerry Dodge

Answer 1

我会这样做：

1. 将数字1至49放入数组中。
2. 对数组进行洗牌。
3. 取出前6个元素。

这可能不是最高效的方法，但易于实现、易于理解，并且最重要的是易于推断抽样方法的分布特性。

对于洗牌，请使用Fisher-Yates shuffle。我用以下通用方法来实现：

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;

这段代码中，Uniform(N) 是一个随机数生成器函数，返回一个从 0..N-1 的均匀分布中抽取的值。你可以在你的代码中将其替换为 Random。而 TGeneric.Swap<T> 则是交换两个元素。

如果你想要对整数数组进行操作，可以这样修改代码：

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;

当然，你只需要执行循环的前六次迭代，因此一个非常高效的版本应该是这样的：

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;

您会称之为传递 6 和 49：

Values := Choose(6, 49);

如果您是一个对性能要求特别高的人，那么我认为很难超过这个：

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;

我应该说，我怀疑性能将成为主导因素。

- David Heffernan

---

我更喜欢非指针版本。 - Warren P

@WarrenP 我试图覆盖所有可能的情况！;-) - David Heffernan

如果我使用 High，我也会使用 Low -> for i := Low( Result ) to High( Result ) do - Sir Rufo

Answer 2

我认为对于一个简单的解决方案，考虑到您需要的值相对较少，而可能的值的数量很大，您可以直接采用暴力解决方法。

如果这是Perl或PHP，我会使用关联数组，但泛型也可以：

uses
  System.Generics.Collections;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
  numbers: TList<Integer>;
  num: Integer;
  output: String;
begin
  numbers := TList<Integer>.Create;
  try
    // We need six integers
    for i := 1 to 6 do
    begin
      // Generate a "random" integer
      num := Random(49) + 1;
      // Keep going until it isn't in our list
      while numbers.Contains(num) do
      begin
        num := Random(49) + 1;
      end;
      // Add it to the list
      numbers.Add(num);
    end;
    // Display the list
    output := '';
    for num in numbers do
    begin
      output := output + IntToStr(num) + ':';
    end;
    ShowMessage(output);
  finally
    numbers.Free;
  end;
end;

这个解决方案可能会引起一些争议，因为有些人可能认为这理论上是不可能发生的，但考虑到Delphi的PRNG，这种情况不会发生。

- Marcus Adams

---

考虑到洗牌整数列表的简易性，我会选择这种方法。 - Warren P