delphi - 总数相等的随机数

Question

我有4个号码

a,b,c,d : integers

我需要为每个数字分配一个 2-7 之间的随机数，但所有四个数字的总和必须为 22

我该怎么做？

Answer 1

首先，我要澄清的是，如上所述，这个问题并没有唯一地定义问题。您要求随机抽样，但没有指定所需的样本分布。

当您实际上表示均匀分布时，却说随机，这是对数学术语的常见滥用。所以我假设这就是你的意思。具体来说，您希望所有可能的不同 4 个数字组具有相同的选择概率。实现这一目标的最简单、最有效的方法如下:

• 枚举所有可能的 4 个数字组。
• 数一下这些数字组，假设为 N。
• 要进行采样，请从 0 到 N-1 范围内的均匀分布中选择随机数。
• 返回第 i 组 4 个数字。

可能的不同集合的列表很小。我凭直觉猜想大概有 50 名候选人。

生成候选人列表非常简单。只需运行从 2 到 7 的三个嵌套 for 循环即可。这将为您提供前三个数字的组合。将它们相加，然后从 22 中减去，然后检查最终数字是否在范围内。

<小时/>

既然你似乎喜欢看代码，这里有一个简单的演示:

{$APPTYPE CONSOLE}

uses
  System.Math,
  Generics.Collections;

type
  TValue = record
    a, b, c, d: Integer;
    procedure Write;
  end;

procedure TValue.Write;
begin
  Writeln(a, ' ', b, ' ', c, ' ', d);
end;

var
  Combinations: TArray<TValue>;

procedure InitialiseCombinations;
var
  a, b, c, d: Integer;
  Value: TValue;
  List: TList<TValue>;
begin
  List := TList<TValue>.Create;
  try
    for a := 2 to 7 do
      for b := 2 to 7 do
        for c := 2 to 7 do
        begin
          d := 22 - a - b - c;
          if InRange(d, 2, 7) then
          begin
            Value.a := a;
            Value.b := b;
            Value.c := c;
            Value.d := d;
            List.Add(Value);
          end;
        end;
    Combinations := List.ToArray;
  finally
    List.Free;
  end;
end;

function GetSample: TValue;
begin
  Result := Combinations[Random(Length(Combinations))];
end;

var
  i: Integer;

begin
  Randomize;
  InitialiseCombinations;
  for i := 1 to 25 do
    GetSample.Write;
  Readln;
end.

<小时/>

从检查中可以清楚地看出，该算法从可用值中均匀采样。

但是其他提出的算法呢？我们可以通过重复采样并计算每个可能样本产生的次数来执行粗略的启发式测试。这是:

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Math,
  Generics.Collections;

type
  TValue = record
    a, b, c, d: Integer;
    procedure Write;
    class operator Equal(const lhs, rhs: TValue): Boolean;
  end;

procedure TValue.Write;
begin
  Writeln(a, ' ', b, ' ', c, ' ', d);
end;

class operator TValue.Equal(const lhs, rhs: TValue): Boolean;
begin
  Result := (lhs.a=rhs.a) and (lhs.b=rhs.b) and (lhs.c=rhs.c) and (lhs.d=rhs.d);
end;

var
  Combinations: TArray<TValue>;

procedure InitialiseCombinations;
var
  a, b, c, d: Integer;
  Value: TValue;
  List: TList<TValue>;
begin
  List := TList<TValue>.Create;
  try
    for a := 2 to 7 do
      for b := 2 to 7 do
        for c := 2 to 7 do
        begin
          d := 22 - a - b - c;
          if InRange(d, 2, 7) then
          begin
            Value.a := a;
            Value.b := b;
            Value.c := c;
            Value.d := d;
            List.Add(Value);
          end;
        end;
    Combinations := List.ToArray;
  finally
    List.Free;
  end;
end;

function GetSampleHeffernan: TValue;
begin
  Result := Combinations[Random(Length(Combinations))];
end;

function GetSampleVanDien: TValue;
const
  TOTAL = 22;
  VALUE_COUNT = 4;
  MIN_VALUE = 2;
  MAX_VALUE = 7;
var
  Values: array[0..VALUE_COUNT-1] of Integer;
  Shortage: Integer;
  Candidates: TList<Integer>;
  ValueIndex: Integer;
  CandidateIndex: Integer;
begin
  Assert(VALUE_COUNT * MAX_VALUE >= TOTAL, 'Total can never be reached!');
  Assert(VALUE_COUNT * MIN_VALUE <= TOTAL, 'Total is always exceeded!');
  Randomize;
  Candidates := TList<Integer>.Create;
  try
    for ValueIndex := 0 to VALUE_COUNT-1 do
    begin
      Values[ValueIndex] := MIN_VALUE;
      Candidates.Add(ValueIndex);
    end;
    Shortage := TOTAL - VALUE_COUNT * MIN_VALUE;
    while Shortage > 0 do
    begin
      CandidateIndex := Random(Candidates.Count);
      ValueIndex := Candidates[CandidateIndex];
      Values[ValueIndex] := Values[ValueIndex] + 1;
      if Values[ValueIndex] = MAX_VALUE then
        Candidates.Remove(CandidateIndex);
      Shortage := Shortage - 1;
    end;
  finally
    Candidates.Free;
  end;

  Result.a := Values[0];
  Result.b := Values[1];
  Result.c := Values[2];
  Result.d := Values[3];
end;

function GetSampleLama: TValue;
type
  TRandomValues = array[1..4] of Integer;
var
  IntSum: Integer;
  Values: TRandomValues;
begin
  // initialize a helper variable for calculating sum of the generated numbers
  IntSum := 0;
  // in the first step just generate a number in the range of 2 to 7 and store
  // it to the first integer element
  Values[1] := RandomRange(2, 7);
  // and increment the sum value
  IntSum := IntSum + Values[1];
  // as the next step we need to generate number, but here we need also say in
  // which range by the following rules to ensure we ever reach 22 (consider, if
  // the 1st number was e.g. 3, then you can't generate the second number smaller
  // than 5 because then even if the next two numbers would be max, you would get
  // e.g. only 3 + 4 + 7 + 7 = 21, so just use this rule:
  // Values[1] Values[2]
  //        2      6..7
  //        3      5..7
  //        4      4..7
  //        5      3..7
  //     6..7      2..7
  Values[2] := RandomRange(Max(2, 8 - Values[1]), 7);
  // and increment the sum value
  IntSum := IntSum + Values[2];
  // if the third step we need to generate a value in the range of 15 to 20 since
  // the fourth number can be still in the range of 2 to 7 which means that the sum
  // after this step must be from 22-7 to 22-2 which is 15 to 20, so let's generate
  // a number which will fit into this sum
  Values[3] := RandomRange(Max(2, Min(7, 15 - IntSum)), Max(2, Min(7, 20 - IntSum)));
  // and for the last number let's just take 22 and subtract the sum of all previous
  // numbers
  Values[4] := 22 - (IntSum + Values[3]);

  Result.a := Values[1];
  Result.b := Values[2];
  Result.c := Values[3];
  Result.d := Values[4];
end;

function IndexOf(const Value: TValue): Integer;
begin
  for Result := 0 to high(Combinations) do
    if Combinations[Result] = Value then
      exit;
  raise EAssertionFailed.Create('Invalid value');
end;

procedure CheckCounts(const Name: string; const GetSample: TFunc<TValue>);
const
  N = 1000000;
var
  i: Integer;
  Counts: TArray<Integer>;
  Range: Integer;
begin
  SetLength(Counts, Length(Combinations));
  for i := 1 to N do
    inc(Counts[IndexOf(GetSample)]);
  Range := MaxIntValue(Counts) - MinIntValue(Counts);
  Writeln(Name);
  Writeln(StringOfChar('-', Length(Name)));
  Writeln(Format('Range = %d, N = %d', [Range, N]));
  Writeln;
end;

begin
  Randomize;
  InitialiseCombinations;
  CheckCounts('Heffernan', GetSampleHeffernan);
  //CheckCounts('Van Dien', GetSampleVanDien);
  CheckCounts('Lama', GetSampleLama);
  Readln;
end.

一次特定运行的输出是:

Heffernan---------Range = 620, N = 1000000Lama----Range = 200192, N = 1000000

The Van Dien variant is commented out at the moment since it produces invalid values.

---

OK, I debugged and fixed the Van Dien variant. The test and results now look like this:

{$APPTYPE CONSOLE}

uses
  System.SysUtils,
  System.Math,
  Generics.Collections;

type
  TValue = record
    a, b, c, d: Integer;
    procedure Write;
    class operator Equal(const lhs, rhs: TValue): Boolean;
  end;

procedure TValue.Write;
begin
  Writeln(a, ' ', b, ' ', c, ' ', d);
end;

class operator TValue.Equal(const lhs, rhs: TValue): Boolean;
begin
  Result := (lhs.a=rhs.a) and (lhs.b=rhs.b) and (lhs.c=rhs.c) and (lhs.d=rhs.d);
end;

var
  Combinations: TArray<TValue>;

procedure InitialiseCombinations;
var
  a, b, c, d: Integer;
  Value: TValue;
  List: TList<TValue>;
begin
  List := TList<TValue>.Create;
  try
    for a := 2 to 7 do
      for b := 2 to 7 do
        for c := 2 to 7 do
        begin
          d := 22 - a - b - c;
          if InRange(d, 2, 7) then
          begin
            Value.a := a;
            Value.b := b;
            Value.c := c;
            Value.d := d;
            List.Add(Value);
          end;
        end;
    Combinations := List.ToArray;
  finally
    List.Free;
  end;
end;

function GetSampleHeffernan: TValue;
begin
  Result := Combinations[Random(Length(Combinations))];
end;

function GetSampleVanDien: TValue;
const
  TOTAL = 22;
  VALUE_COUNT = 4;
  MIN_VALUE = 2;
  MAX_VALUE = 7;
var
  Values: array[0..VALUE_COUNT-1] of Integer;
  Shortage: Integer;
  Candidates: TList<Integer>;
  ValueIndex: Integer;
  CandidateIndex: Integer;
begin
  Assert(VALUE_COUNT * MAX_VALUE >= TOTAL, 'Total can never be reached!');
  Assert(VALUE_COUNT * MIN_VALUE <= TOTAL, 'Total is always exceeded!');
  Candidates := TList<Integer>.Create;
  try
    for ValueIndex := 0 to VALUE_COUNT-1 do
    begin
      Values[ValueIndex] := MIN_VALUE;
      Candidates.Add(ValueIndex);
    end;
    Shortage := TOTAL - VALUE_COUNT * MIN_VALUE;
    while Shortage > 0 do
    begin
      CandidateIndex := Random(Candidates.Count);
      ValueIndex := Candidates[CandidateIndex];
      inc(Values[ValueIndex]);
      if Values[ValueIndex] = MAX_VALUE then
        Candidates.Delete(CandidateIndex);
      dec(Shortage);
    end;
  finally
    Candidates.Free;
  end;

  Result.a := Values[0];
  Result.b := Values[1];
  Result.c := Values[2];
  Result.d := Values[3];
end;

function GetSampleLama: TValue;
type
  TRandomValues = array[1..4] of Integer;
var
  IntSum: Integer;
  Values: TRandomValues;
begin
  // initialize a helper variable for calculating sum of the generated numbers
  IntSum := 0;
  // in the first step just generate a number in the range of 2 to 7 and store
  // it to the first integer element
  Values[1] := RandomRange(2, 7);
  // and increment the sum value
  IntSum := IntSum + Values[1];
  // as the next step we need to generate number, but here we need also say in
  // which range by the following rules to ensure we ever reach 22 (consider, if
  // the 1st number was e.g. 3, then you can't generate the second number smaller
  // than 5 because then even if the next two numbers would be max, you would get
  // e.g. only 3 + 4 + 7 + 7 = 21, so just use this rule:
  // Values[1] Values[2]
  //        2      6..7
  //        3      5..7
  //        4      4..7
  //        5      3..7
  //     6..7      2..7
  Values[2] := RandomRange(Max(2, 8 - Values[1]), 7);
  // and increment the sum value
  IntSum := IntSum + Values[2];
  // if the third step we need to generate a value in the range of 15 to 20 since
  // the fourth number can be still in the range of 2 to 7 which means that the sum
  // after this step must be from 22-7 to 22-2 which is 15 to 20, so let's generate
  // a number which will fit into this sum
  Values[3] := RandomRange(Max(2, Min(7, 15 - IntSum)), Max(2, Min(7, 20 - IntSum)));
  // and for the last number let's just take 22 and subtract the sum of all previous
  // numbers
  Values[4] := 22 - (IntSum + Values[3]);

  Result.a := Values[1];
  Result.b := Values[2];
  Result.c := Values[3];
  Result.d := Values[4];
end;

function IndexOf(const Value: TValue): Integer;
begin
  for Result := 0 to high(Combinations) do
    if Combinations[Result] = Value then
      exit;
  raise EAssertionFailed.Create('Invalid value');
end;

procedure CheckCounts(const Name: string; const GetSample: TFunc<TValue>);
const
  N = 1000000;
var
  i: Integer;
  Counts: TArray<Integer>;
  Range: Integer;
begin
  SetLength(Counts, Length(Combinations));
  for i := 1 to N do
    inc(Counts[IndexOf(GetSample)]);
  Range := MaxIntValue(Counts) - MinIntValue(Counts);
  Writeln(Name);
  Writeln(StringOfChar('-', Length(Name)));
  Writeln(Format('Range = %d, N = %d', [Range, N]));
  Writeln;
end;

begin
  Randomize;
  InitialiseCombinations;
  CheckCounts('Heffernan', GetSampleHeffernan);
  CheckCounts('Van Dien', GetSampleVanDien);
  CheckCounts('Lama', GetSampleLama);
  Readln;
end.

Heffernan---------Range = 599, N = 1000000Van Dien--------Range = 19443, N = 1000000Lama----Range = 199739, N = 1000000

<小时/>

为了让大家明白，这里有一些不同分布的经验概率质量函数图:

<小时/>

好的，现在我修复了@TLama 的代码。它正在使用 RandomRange错误地。 documentation状态:

RandomRange returns a random integer from the range that extends between AFrom and ATo (non-inclusive).

关键是范围被定义为闭开区间。返回值的范围是[AFrom..ATo)，或者用不等号表示，AFrom <= Value < ATo。

但是@TLama的代码是在区间两端闭合的假设下编写的。因此，可以通过在每次调用 RandomRange 的第二个参数中添加 1 来轻松修复代码。当我们这样做时，输出如下所示:

Heffernan---------Range = 587, N = 1000000Van Dien--------Range = 19425, N = 1000000Lama----Range = 79320, N = 1000000

经验 PMF 图变为:

<小时/>

所有这一切的底线是，如果您关心分布，则很难获得正确的采样。