私は4つの番号を持っています
a,b,c,d : integers
それぞれに 2 ～ 7 の乱数を割り当てる必要がありますが、4 つの数字すべての合計は 22 でなければなりません
これどうやってするの？
質問する
659 次
3 に答える
8
まず第一に、述べたように、質問が問題を一意に定義するものではないことを明確にします。ランダム サンプリングを要求しますが、サンプルの目的の分布を指定しません。
実際には一様分布を意味するときにランダムと言うのは、数学用語のよくある乱用です。だから私はそれがあなたの言いたいことだと思います。具体的には、可能なすべての異なる 4 つの数値のセットの選択確率が等しくなるようにします。これを実現する最も簡単で効率的な方法は次のとおりです。
- そのような 4 つの数の可能なセットをすべて列挙します。
- これらの数のセットを数えて、N とします。
- サンプリングするには、範囲0からN-1の一様分布から乱数を選択します。
- 4 つの数値の i 番目のセットを返します。
可能な個別のセットのリストは少ないです。私の頭の上では、約50人の候補者がいると思います。
候補リストの生成は非常に簡単です。ネストされた for ループを 2 から 7 まで 3 回実行するだけです。これにより、最初の 3 つの数値の組み合わせが得られます。それらを合計し、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 バリアントは、無効な値を生成するため、現時点ではコメントアウトされています。
OK、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
念のため、さまざまな分布の経験的確率質量関数のプロットをいくつか示します。
OK、@TLama のコードを修正しました。使い方がRandomRange間違っていました。ドキュメントには次のように記載されています。
RandomRange は、AFrom と ATo (非包括的) の間の範囲からランダムな整数を返します。
重要なのは、範囲がクローズド-オープン間隔として定義されていることです。返される値は、[AFrom..ATo) の範囲内にあるか、不等号 AFrom <= Value < ATo で表されます。
しかし、@TLama のコードは、間隔が両端で閉じていることを前提に書かれています。したがって、各呼び出しの 2 番目のパラメーターに 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;
4 つの数値はすべて最小値に初期化されます。次に、合計に達していない間に、まだ増やすことができる数字の 1 つをランダムに選択し、1 つ増やします。
于 2013-10-19T14:55:49.130 に答える
2
考えられるすべてのサンプルのテーブルを作成する必要のない効率的な代替手段は、次のとおりです。
- [2..7] の範囲で 3 つの値を選択します。
- 4 番目の値を 22 から最初の 3 つの合計を差し引いた値に設定します。
- 4 番目の値が [2..7] の範囲にない場合は、1 に進みます。
- 4 つの値を返します。
コーディングは単純で、最初の回答と同じ構造を使用しています。
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 に答える