我有4个号码
a,b,c,d : integers
我需要为每个数字分配一个 2-7 之间的随机数，但所有四个数字的总和必须为 22
我怎样才能做到这一点？
问问题
659 次
3 回答
8
首先，我要明确指出，如前所述，问题并没有唯一地定义问题。您要求随机抽样，但没有指定所需的样本分布。
当您实际上是指均匀分布时，说随机是数学术语的常见滥用。所以我假设这就是你的意思。具体来说，您希望所有可能不同的 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.
一次特定运行的输出是：
赫弗南 --------- 范围 = 620，N = 1000000 喇嘛 ---- 范围 = 200192，N = 1000000
Van Dien 变体目前已被注释掉，因为它会产生无效值。
好的，我调试并修复了 Van Dien 变体。测试和结果现在看起来像这样：
{$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.
赫弗南 --------- 范围 = 599，N = 1000000 范迪恩 -------- 范围 = 19443，N = 1000000 喇嘛 ---- 范围 = 199739，N = 1000000
只是为了把它撞回家，这里有一些各种分布的经验概率质量函数图：
好的，现在我修复了@TLama 的代码。它使用RandomRange不正确。该文档指出：
RandomRange 从 AFrom 和 ATo（不包括在内）之间扩展的范围返回一个随机整数。
关键是范围被定义为闭开区间。返回的值在 [AFrom..ATo) 范围内，或者用不等号表示，AFrom <= Value < ATo。
但是@TLama 的代码是在假设区间两端都闭合的情况下编写的。因此，可以通过在每次调用的第二个参数上加 1 来轻松修复代码RandomRange。当我们这样做时，输出如下所示：
赫弗南 --------- 范围 = 587，N = 1000000 范迪恩 -------- 范围 = 19425，N = 1000000 喇嘛 ---- 范围 = 79320，N = 1000000
经验 PMF 图变为：
所有这一切的底线是，如果您关心分布，则很难正确采样。
于 2013-10-19T12:55:06.773 回答
2
警告：@DavidHeffernan 已证明此解决方案不统一。
22 是一个相当低的数字，所以以下应该可以很好地工作：
procedure ShowValues;
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;
ShowMessage(IntToStr(Values[0]) + ' ' + IntToStr(Values[1]) +
' ' + IntToStr(Values[2]) + ' ' + IntToStr(Values[3]));
end;
所有四个数字都被初始化为最小值。然后，虽然我们还没有达到总数，但我们随机选择一个可能仍会增加的数字并将其增加一。
于 2013-10-19T14:55:49.130 回答
2
一个有效的替代方案，不涉及构建所有可能样本的表，如下所示：
- 在范围 [2..7] 中选择三个值。
- 将第四个值设置为等于 22 减去前三个值的总和。
- 如果第四个值不在 [2..7] 范围内，则转到 1。
- 返回四个值。
编码很简单，并且使用与我的第一个答案相同的结构：
function GetSample: TValue;
begin
repeat
Result.a := RandomRange(2, 8);
Result.b := RandomRange(2, 8);
Result.c := RandomRange(2, 8);
Result.d := 22 - Result.a - Result.b- Result.c;
until InRange(Result.d, 2, 7);
end;
经验概率质量，使用与我的第一个答案相同的测试工具，如下所示：
于 2013-10-20T11:29:52.343 回答