1 から 5 の範囲のランダムな整数を生成する関数が与えられた場合、1 から 7 の範囲のランダムな整数を生成する関数を作成します。
- 簡単な解決策は何ですか？
- メモリ使用量を減らしたり、低速の CPU で実行したりするための効果的なソリューションは何ですか?
214541 次
77 に答える
592
これはAdamRosenfieldのソリューションと同等ですが、一部の読者にとってはもう少し明確かもしれません。rand5（）は、1から5までの範囲の統計的にランダムな整数を返す関数であると想定しています。
int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
それはどのように機能しますか？このように考えてください。この2次元配列を紙に印刷し、ダーツボードに貼り付けて、ランダムにダーツを投げるところを想像してみてください。ゼロ以外の値をヒットした場合、選択できるゼロ以外の値の数は同じであるため、1から7の間の統計的にランダムな値になります。ゼロに当たった場合は、ゼロ以外に当たるまでダーツを投げ続けます。これがこのコードの機能です。iインデックスとjインデックスはダーツボード上の場所をランダムに選択し、良い結果が得られない場合はダーツを投げ続けます。
アダムが言ったように、これは最悪の場合に永遠に実行される可能性がありますが、統計的に最悪の場合は決して起こりません。:)
于 2009-05-08T22:59:54.800 に答える
365
1/7 は基数 5 の無限小数であるため、一定時間内に実行される (正確に正しい) ソリューションはありません。単純なソリューションの 1 つは、棄却サンプリングを使用することです。たとえば、次のようになります。
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
これには、ループの 25/21 = 1.19 回の反復の実行時間が予想されますが、永遠にループする可能性はごくわずかです。
于 2008-09-26T04:41:59.767 に答える
153
最初の回答に加えて、別の回答を追加したいと思います。この回答は、 への呼び出しrand5()ごとの への呼び出しの数を最小限に抑え、rand7()ランダム性の使用を最大化しようとします。つまり、ランダム性が貴重なリソースであると考える場合、ランダムなビットを捨てずに、可能な限りそれを使用したいと考えています。この回答には、 Ivan's answerに示されているロジックとの類似点もあります。
確率変数のエントロピーは明確に定義された量です。等しい確率 (一様分布) で N 個の状態をとる確率変数の場合、エントロピーは log 2 N です。したがって、rand5()約 2.32193 ビットのエントロピーがあり、rand7()約 2.80735 ビットのエントロピーがあります。ランダム性を最大限に利用したい場合は、 への各呼び出しから 2.32193 ビットのエントロピーをすべて使用しrand5()、それらを への各呼び出しに必要な 2.80735 ビットのエントロピーの生成に適用する必要がありますrand7()。rand5()したがって、基本的な制限は、 への呼び出しごとに log(7)/log(5) = 1.20906 への呼び出しを超えることはできないということですrand7()。
補足: 特に指定のない限り、この回答のすべての対数は底 2 になります。 rand5()範囲 [0, 4] のrand7()数値を返すと想定され、範囲 [0, 6] の数値を返すと想定されます。範囲をそれぞれ [1, 5] と [1, 7] に調整するのは簡単です。
では、どうすればよいのでしょうか。0 と 1 の間の無限に正確な乱数の実数を生成します(このような無限に正確な数を実際に計算して保存できると仮定してください。これは後で修正します)。このような数値は、基数5で数字を生成することによって生成できます。乱数 0.1 a2 a3 ... を選択します。ここで、各数字 aは への呼び出しによって選択されます。たとえば、RNG がall に対して a = 1 を選択した場合、それがあまりランダムではないという事実を無視すると、それは実数 1/5 + 1/5 2 + 1/5 3 + ... =に対応します。 1/4 (等比級数の合計)。airand5()ii
では、0 から 1 の間のランダムな実数を選択しました。このような乱数は一様に分布していると主張します。直感的には、各桁が均一に選択されており、数値が無限に正確であるため、これは簡単に理解できます。ただし、離散分布ではなく連続分布を扱っているため、これの正式な証明はやや複雑です。そのため、数値が区間 [ a, b] にある確率が の長さに等しいことを証明する必要があります。その間隔、b - a. 証明は読者の演習として残します =)。
範囲 [0, 1] から均一に選択された乱数の実数を取得したので、それを範囲 [0, 6] の一連の均一乱数に変換して の出力を生成する必要がありますrand7()。どうやってこれを行うのですか？ちょうど今行ったことの逆です。これを基数 7 の無限に正確な 10 進数に変換すると、基数 7 の各桁が の 1 つの出力に対応しますrand7()。
前の例で言えば、rand5()1 の無限ストリームを生成する場合、ランダムな実数は 1/4 になります。1/4 を底 7 に変換すると、無限小数 0.15151515... が得られるので、出力として 1、5、1、5、1、5 などを生成します。
さて、これで主なアイデアはわかりましたが、2 つの問題が残っています: 無限に正確な実数を実際に計算したり保存したりすることはできません。第二に、実際にそれを基数 7 に変換するにはどうすればよいでしょうか?
0 から 1 までの数値を基数 7 に変換する 1 つの方法は次のとおりです。
- 7 を掛ける
- 結果の整数部分は、次の基数 7 桁です。
- 整数部分を引き、小数部分だけを残す
- ステップ 1 に進む
無限の精度の問題に対処するために、部分的な結果を計算し、結果の上限も格納します。つまり、rand5()2 回呼び出して、両方とも 1 を返したとします。これまでに生成した数値は 0.11 (基数 5) です。残りの無限の一連の呼び出しがrand5()生成されても、生成する乱数の実数は 0.12 より大きくなることはありません: 0.11 ≤ 0.11xyz... < 0.12 は常に真です。
したがって、これまでの現在の数値とその最大値を追跡しながら、両方の数値を基数 7 に変換します。最初の桁が一致していれば、次の桁kを安全に出力できます。k基数 5 の数字の無限ストリームはk、基数 7 表現の次の数字に影響を与えることはありません!
これがアルゴリズムです -- の次の出力を生成するために、乱数の実数を基数 7 に変換する際に、次の桁の値を確実に知るために必要なrand7()数の のみを生成します。rand5()テスト ハーネスを使用した Python 実装:
import random
rand5_calls = 0
def rand5():
global rand5_calls
rand5_calls += 1
return random.randint(0, 4)
def rand7_gen():
state = 0
pow5 = 1
pow7 = 7
while True:
if state / pow5 == (state + pow7) / pow5:
result = state / pow5
state = (state - result * pow5) * 7
pow7 *= 7
yield result
else:
state = 5 * state + pow7 * rand5()
pow5 *= 5
if __name__ == '__main__':
r7 = rand7_gen()
N = 10000
x = list(next(r7) for i in range(N))
distr = [x.count(i) for i in range(7)]
expmean = N / 7.0
expstddev = math.sqrt(N * (1.0/7.0) * (6.0/7.0))
print '%d TRIALS' % N
print 'Expected mean: %.1f' % expmean
print 'Expected standard deviation: %.1f' % expstddev
print
print 'DISTRIBUTION:'
for i in range(7):
print '%d: %d (%+.3f stddevs)' % (i, distr[i], (distr[i] - expmean) / expstddev)
print
print 'Calls to rand5: %d (average of %f per call to rand7)' % (rand5_calls, float(rand5_calls) / N)
ジェネレーターを返すことに注意してくださいrand7_gen()。これは、数値を基数 7 に変換する内部状態があるためです。テスト ハーネスは、next(r7)10000 回呼び出して 10000 個の乱数を生成し、その分布を測定します。整数演算のみが使用されるため、結果は正確です。
また、ここの数値は非常に大きく、非常に速くなることに注意してください。5 と 7 の累乗は急速に大きくなります。そのため、大量の乱数を生成すると、bignum 演算によりパフォーマンスが著しく低下し始めます。ただし、ここでの目標はランダム ビットの使用を最大化することであり、パフォーマンスを最大化することではありません (ただし、これは二次的な目標です)。
これを 1 回実行すると、rand5()を 10000回呼び出して を 12091 回呼び出しrand7()、平均して有効数字 4 桁の最小 log(7)/log(5) 呼び出しを達成し、結果の出力は均一でした。
このコードを、任意に大きな整数が組み込まれていない言語に移植するには、値pow5をpow7ネイティブの整数型の最大値に制限する必要があります。値が大きくなりすぎた場合は、リセットします。すべてをやり直します。これにより、呼び出しごとの平均呼び出し数がrand5()わずかrand7()に増加しますが、32 ビットまたは 64 ビットの整数の場合でも、あまり増加しないことを願っています。
于 2009-05-21T03:38:42.107 に答える
36
( Adam Rosenfeld の回答を盗み、約 7% 高速に実行しました。)
rand5() が {0,1,2,3,4} のいずれかを均等に分配して返し、目標が均等に分配された {0,1,2,3,4,5,6} を返すとします。
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
ループが変数で作成できる最大値を追跡していますmax。これまでの結果が max%7 と max-1 の間にある場合、結果はその範囲内で均一に分散されます。そうでない場合は、0 と max%7-1 の間でランダムな剰余を使用し、rand() をもう一度呼び出して、新しい数値と新しい最大値を作成します。それからまた始めます。
編集: rand5() を呼び出す回数は、次の式の x であると予想されます。
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
于 2009-04-30T13:56:02.747 に答える
30
アルゴリズム：
7 は 3 ビットのシーケンスで表すことができます
rand(5) を使用して、各ビットをランダムに 0 または 1 で埋めます。
たとえば、rand(5) を呼び出して、
結果が 1 または 2 の
場合、結果が 4 または 5 の場合はビットを 0 で埋め
、結果が 3 の場合はビットを 1 で埋め、無視してやり直す (拒否)
このようにして、3 ビットをランダムに 0/1 で埋めて、1 ～ 7 の数値を得ることができます。
編集: これは最も単純で最も効率的な答えのように思われるので、そのためのコードを次に示します。
public static int random_7() {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + random_5_output_2();
}
}
return returnValue;
}
private static int random_5_output_2() {
while (true) {
int flip = random_5();
if (flip < 3) {
return 0;
}
else if (flip > 3) {
return 1;
}
}
}
于 2010-11-14T21:23:08.463 に答える
19
int randbit( void )
{
while( 1 )
{
int r = rand5();
if( r <= 4 ) return(r & 1);
}
}
int randint( int nbits )
{
int result = 0;
while( nbits-- )
{
result = (result<<1) | randbit();
}
return( result );
}
int rand7( void )
{
while( 1 )
{
int r = randint( 3 ) + 1;
if( r <= 7 ) return( r );
}
}
于 2008-09-26T05:03:20.293 に答える
18
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
編集：それはうまくいきません。1000 分の 2 程度ずれています (完全な rand5 を想定)。バケットは次を取得します。
value Count Error%
1 11158 -0.0035
2 11144 -0.0214
3 11144 -0.0214
4 11158 -0.0035
5 11172 +0.0144
6 11177 +0.0208
7 11172 +0.0144
の合計に切り替えることにより、
n Error%
10 +/- 1e-3,
12 +/- 1e-4,
14 +/- 1e-5,
16 +/- 1e-6,
...
28 +/- 3e-11
2を追加するごとに1桁大きくなるようです
ところで：上記のエラーの表は、サンプリングによって生成されたのではなく、次の再帰関係によって生成されました。
p[x,n]への呼び出しがoutput=x与えられた場合に発生する可能性のある方法の数です。nrand5
p[1,1] ... p[5,1] = 1
p[6,1] ... p[7,1] = 0
p[1,n] = p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1]
p[2,n] = p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1] + p[4,n-1]
p[3,n] = p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1] + p[5,n-1]
p[4,n] = p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1] + p[6,n-1]
p[5,n] = p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1] + p[7,n-1]
p[6,n] = p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1] + p[1,n-1]
p[7,n] = p[6,n-1] + p[5,n-1] + p[4,n-1] + p[3,n-1] + p[2,n-1]
于 2008-09-26T04:51:38.853 に答える
16
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
于 2008-09-26T04:48:00.720 に答える
13
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
選択したソリューションとは異なり、アルゴリズムは一定時間で実行されます。ただし、選択したソリューションの平均実行時間よりも 2 回多く rand5 を呼び出します。
このジェネレーターは完全ではないことに注意してください (数値 0 は他の数値よりも 0.0064% 高い可能性があります) が、ほとんどの実用的な目的では、一定の時間の保証はおそらくこの不正確さを上回ります。
説明
この解は、数値 15,624 が 7 で割り切れるという事実から導き出されます。したがって、0 から 15,624 までの数値をランダムかつ一様に生成し、mod 7 を取ることができれば、ほぼ一様な rand7 ジェネレーターを得ることができます。0 から 15,624 までの数値は、次のように rand5 を 6 回ローリングし、それらを使用して基数 5 の数字を形成することによって均一に生成できます。
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
ただし、mod 7 のプロパティにより、方程式を少し簡略化できます。
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
そう
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
になる
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
仮説
数 15,624 は無作為に選択されたわけではありませんが、p が素数である場合、フェルマーの小定理を使用して発見できます。
a^(p-1) = 1 mod p
これにより、
(5^6)-1 = 0 mod 7
(5^6)-1 は次の値に等しい
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
これは基数 5 形式の数値であるため、このメソッドを使用して任意の乱数ジェネレーターから他の乱数ジェネレーターに移動できることがわかります。ただし、指数 p-1 を使用すると、0 への小さなバイアスが常に導入されます。
このアプローチを一般化し、より正確にするために、次のような関数を使用できます。
def getRandomconverted(frm, to):
s = 0
for i in range(to):
s += getRandomUniform(frm)*frm**i
mx = 0
for i in range(to):
mx = (to-1)*frm**i
mx = int(mx/to)*to # maximum value till which we can take mod
if s < mx:
return s%to
else:
return getRandomconverted(frm, to)
于 2015-11-19T05:16:30.047 に答える
13
以下は、{1, 2, 3, 4, 5} で一様分布を生成する乱数ジェネレーターを使用して、{1, 2, 3, 4, 5, 6, 7} で一様分布を生成します。コードはごちゃごちゃしていますが、ロジックは明確です。
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
于 2009-01-15T04:18:34.913 に答える
12
最も効率的な答えを与えようとする追加の制約を考慮すると、つまり、 1 ～ 5Iの長さの均一に分散された整数の入力ストリーム が与えられた場合、相対的に最長の長さの 1 ～ 7 の均一に分散された整数mのストリーム が出力されます。Oとm、言うL(m)。
これを分析する最も簡単な方法は、ストリーム I とOをそれぞれ 5 進数と 7 進数として扱うことです。これは、ストリームを取得するという主な回答のアイデアによって実現され、a1, a2, a3,... -> a1+5*a2+5^2*a3+..同様にストリームについても実現されますO。
m choose n s.t. 5^m-7^n=c次に、 とがc>0できるだけ小さい長さの入力ストリームのセクションを取得するとします。次に、長さ m の入力ストリームから to の整数1へ5^mの一様なマップと、1 から7^n長さ n の出力ストリームへの別の一様なマップがあり、マップされた整数が入力ストリームからいくつかのケースを失う必要があるかもしれませんを超えて7^nいます。
したがって、これは約L(m)のの値を示します。m (log5/log7).82m
上記の解析の難しさは、5^m-7^n=c正確に解くのが容易でない方程式と、 から までの一様な値が1を5^m超え7^nて効率が低下する場合です。
問題は、可能な限り最高の m 値 (log5/log7) にどれだけ近づけるかです。たとえば、この数値が整数に近づくと、この正確な整数の出力値を達成する方法を見つけることができますか?
次に、入力ストリームからから5^m-7^n=c一様乱数を効果的に生成し、より大きい値は使用しません。ただし、これらの値はレスキューして再度使用することができます。それらは、1 から までの均一な数列を効果的に生成します。そのため、これらを使用して 7 進数に変換し、より多くの出力値を作成できるようにします。 0(5^m)-17^n5^m-7^n
サイズ の一様な入力から導出された整数T7(X)の出力シーケンスの平均長を とすると、 と仮定します。random(1-7)X5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7
次にT7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)、確率 7^n0/5^m の長さのシーケンスがないため、確率 の長さの残差があり5^m-7^n0ます(5^m-7^n0)/5^m)。
代入を続けると、次のようになります。
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
したがって
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
これを置く別の方法は次のとおりです。
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
考えられる最良のケースは、 where 5^m=7^n+s、 whereの上の私のオリジナルのものs<7です。
その後T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)は元通り。
最悪のケースは、k と st 5^m = kx7+s しか見つからない場合です。
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
他のケースはその中間です。非常に大きな m に対してどれだけうまく処理できるか、つまり誤差項をどれだけうまく取得できるかを見るのは興味深いでしょう。
T7(5^m) = m (Log5/Log7)+e(m)
一般的に達成することは不可能に思えe(m) = o(1)ますが、うまくいけば証明できe(m)=o(m)ます。
5^m全体は、 のさまざまな値に対するの 7 進数字の分布に基づいていますm。
これをカバーする多くの理論がそこにあると確信しています。私は見て、ある時点で報告するかもしれません.
于 2009-05-09T00:11:35.297 に答える
12
宿題の問題はここで許可されますか?
この関数は、大雑把な「基数 5」の計算を行い、0 から 6 までの数値を生成します。
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
于 2008-09-26T04:41:39.377 に答える
10
簡単にしてみませんか？
int random7() {
return random5() + (random5() % 3);
}
このソリューションで1と7を取得する可能性はモジュロのために低くなりますが、すばやく読みやすいソリューションが必要な場合は、これが最適な方法です。
于 2009-11-09T12:11:16.173 に答える
10
これは、 Adam の答えの実用的な Python 実装です。
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
調べているアルゴリズムを Python に投げ込むのが好きなので、それらをいじってみることができます。一緒に投げるのに時間がかかったということではなく、そこにいる誰かに役立つことを期待してここに投稿したいと思いました。
于 2009-05-04T04:57:24.180 に答える
8
アダムローゼンフィールドの正解の背後にある前提は次のとおりです。
- x = 5 ^ n（彼の場合：n = 2）
- n rand5呼び出しを操作して、範囲[1、x]内の数値yを取得します。
- z =（（int）（x / 7））* 7
- y> zの場合は、再試行してください。それ以外の場合はy％7+1を返します
nが2に等しい場合、4つの使い捨ての可能性があります：y = {22、23、24、25}。n = 6を使用する場合、使い捨ては1つだけです：y={15625}。
5 ^ 6 = 15625
7 * 2232 = 15624
rand5をさらに何度も呼び出します。ただし、使い捨ての値（または無限ループ）を取得する可能性ははるかに低くなります。yの使い捨て値を取得する方法がない場合、私はまだそれを見つけていません。
于 2009-06-23T14:17:22.637 に答える
8
ここでrand（n）が「 0からn-1まで の一様分布のランダム整数」を意味すると仮定すると、Pythonのrandintを使用したコードサンプルがあります。これはその効果があります。randint（5）と定数のみを使用して、 randint（7）の効果を生成します。少しばかげている、実際には
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
于 2009-04-30T09:39:47.903 に答える
8
これが私の答えです：
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
他のものより少し複雑ですが、rand5 の呼び出しを最小限に抑えることができると思います。他のソリューションと同様に、長時間ループする可能性がわずかにあります。
于 2009-09-09T03:44:47.317 に答える
7
シンプルで効率的:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(あなたのお気に入りの「プログラマー」漫画は何ですか?に触発されました)。
于 2010-08-23T13:14:19.940 に答える
6
1から始まる範囲は好きではないので、0から始めます:-)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
于 2010-09-21T15:45:00.130 に答える
5
答えられたことは知っていますが、これは問題ないようですが、バイアスがあるかどうかはわかりません。私の「テスト」は、少なくともそれが合理的であることを示唆しています。
おそらく、アダム・ローゼンフィールドは親切にコメントしてくれるでしょうか？
私の（ナイーブ？）アイデアはこれです：
rand7を作成するのに十分なランダムビットができるまで、rand5を累積します。これには最大2つのrand5が必要です。rand7番号を取得するには、累積値mod7を使用します。
アキュムレータのオーバーフローを回避するために、またアキュムレータはmod 7であるため、アキュムレータのmod7を使用します。
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
rand7（）関数は次のとおりです。
（rand5の範囲を0〜4とし、rand7も同様に0〜6にします。）
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
編集：1億回の試行の結果を追加しました。
「実際の」rand関数mod5または7
rand5：avg = 1.999802 0：20003944 1：19999889 2：20003690 3：19996938 4：19995539 rand7：avg = 3.000111 0：14282851 1：14282879 2：14284554 3：14288546 4：14292388 5：14288736 6：14280046
私のrand7
平均は問題ないように見え、数の分布も問題ないように見えます。
randt：avg = 3.000080 0：14288793 1：14280135 2：14287848 3：14285277 4：14286341 5：14278663 6：14292943
于 2010-04-19T12:14:52.647 に答える
5
ほら、均一な分布とゼロの rand5 呼び出しです。
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
事前にシードを設定する必要があります。
于 2009-12-29T01:46:23.933 に答える
4
上で引用した洗練されたアルゴリズムがありますが、遠回しになるかもしれませんが、それにアプローチする 1 つの方法を次に示します。0から生成された値を想定しています。
R2 = 2 未満の値を与える乱数発生器 (サンプル空間 = {0, 1})
R8 = 8 未満の値を与える乱数発生器 (サンプル空間 = {0, 1, 2, 3, 4, 5, 6, 7) }))
R2 から R8 を生成するには、R2 を 3 回実行し、3 回の実行すべてを組み合わせた結果を 3 桁の 2 進数として使用します。R2 を 3 回実行したときの値の範囲は次のとおりです。
0 0 0 --> 0
.
.
1 1 1 --> 7
R8 から R7 を生成するには、R7 が 7 を返した場合に再度実行します。
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
回避策は、R5 から R2 を生成し (R8 から R7 を生成したように)、R2 から R8 を生成し、R8 から R7 を生成することです。
于 2009-09-17T23:20:37.377 に答える
4
これは、完全に整数内に収まり、最適値の約 4% 以内である解です (つまり、{0..6} のすべての乱数に対して {0..4} で 1.26 の乱数を使用します)。コードは Scala にありますが、数学はどの言語でもかなり明確なはずです。7^9 + 7^8 が 5^11 に非常に近いという事実を利用します。したがって、基数 5 で 11 桁の数値を選択し、それが範囲内にある場合は基数 7 の 9 桁の数値として解釈し (9 基数 7 の数値を与える)、9 桁を超える場合は 8 桁の数値として解釈します。 .:
abstract class RNG {
def apply(): Int
}
class Random5 extends RNG {
val rng = new scala.util.Random
var count = 0
def apply() = { count += 1 ; rng.nextInt(5) }
}
class FiveSevener(five: RNG) {
val sevens = new Array[Int](9)
var nsevens = 0
val to9 = 40353607;
val to8 = 5764801;
val to7 = 823543;
def loadSevens(value: Int, count: Int) {
nsevens = 0;
var remaining = value;
while (nsevens < count) {
sevens(nsevens) = remaining % 7
remaining /= 7
nsevens += 1
}
}
def loadSevens {
var fivepow11 = 0;
var i=0
while (i<11) { i+=1 ; fivepow11 = five() + fivepow11*5 }
if (fivepow11 < to9) { loadSevens(fivepow11 , 9) ; return }
fivepow11 -= to9
if (fivepow11 < to8) { loadSevens(fivepow11 , 8) ; return }
fivepow11 -= to8
if (fivepow11 < 3*to7) loadSevens(fivepow11 % to7 , 7)
else loadSevens
}
def apply() = {
if (nsevens==0) loadSevens
nsevens -= 1
sevens(nsevens)
}
}
テストをインタープリター (実際には REPL) に貼り付けると、次のようになります。
scala> val five = new Random5
five: Random5 = Random5@e9c592
scala> val seven = new FiveSevener(five)
seven: FiveSevener = FiveSevener@143c423
scala> val counts = new Array[Int](7)
counts: Array[Int] = Array(0, 0, 0, 0, 0, 0, 0)
scala> var i=0 ; while (i < 100000000) { counts( seven() ) += 1 ; i += 1 }
i: Int = 100000000
scala> counts
res0: Array[Int] = Array(14280662, 14293012, 14281286, 14284836, 14287188,
14289332, 14283684)
scala> five.count
res1: Int = 125902876
分布は良好で平坦です (近似ガウス分布から予想されるように、各ビンで 10^8 の 1/7 の約 10k 以内)。
于 2010-03-10T21:25:58.103 に答える
3
PHPで
function rand1to7() {
do {
$output_value = 0;
for ($i = 0; $i < 28; $i++) {
$output_value += rand1to5();
}
while ($output_value != 140);
$output_value -= 12;
return floor($output_value / 16);
}
ループして 16 から 127 の間の乱数を生成し、16 で除算して 1 から 7.9375 の間の float を作成し、切り捨てて 1 から 7 の間の int を取得します。私が間違っていなければ、取得する確率は 16/112 です7つの結果のいずれか。
于 2011-04-01T04:06:43.740 に答える
3
この答えは、Rand5 関数から可能な限り多くのエントロピーを得るための実験です。したがって、t はやや不明確であり、ほぼ確実に他の実装よりもかなり遅くなります。
0 から 4 までの一様分布と、結果として 0 から 6 までの一様分布を仮定すると、次のようになります。
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
Rand5 への呼び出しごとにバッファーに追加されるビット数は、現在 4/5 * 2 なので 1.6 です。1/5 の確率値が含まれている場合、0.05 増加して 1.65 になりますが、これを無効にしなければならなかったコードのコメントを参照してください。
Rand7 の呼び出しで消費されるビット数 = 3 + 1/8 * (3 + 1/8 * (3 + 1/8 * (...
これは 3 + 3/8 + 3/64 + 3/512 ... なので約3.42
セブンから情報を抽出することで、呼び出しごとに 1/8*1/7 ビットを再利用するので、約 0.018 になります。
これにより、呼び出しごとに 3.4 ビットの正味消費が得られます。これは、比率が Rand7 ごとに Rand5 に対する 2.125 呼び出しであることを意味します。最適値は 2.1 です。
Rand5 への呼び出しのコストが非常に高くない限り (エントロピーの外部ソースへの呼び出しなど)、このアプローチは他の多くの方法よりも大幅に遅いと思います。
于 2009-05-13T17:38:16.923 に答える
3
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
于 2010-12-03T01:31:46.060 に答える
3
最初の関数から出力をスケーリングするだけです
0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
于 2010-05-27T08:20:17.473 に答える
2
rand25() =5*(rand5()-1) + rand5()
rand7() {
while(true) {
int r = rand25();
if (r < 21) return r%3;
}
}
これが機能する理由：ループが永久に実行される確率は0です。
于 2011-03-18T15:32:40.590 に答える
2
int getOneToSeven(){
int added = 0;
for(int i = 1; i<=7; i++){
added += getOneToFive();
}
return (added)%7+1;
}
于 2010-11-30T17:22:18.657 に答える
2
function Rand7
put 200 into x
repeat while x > 118
put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
end repeat
return (x mod 7) + 1
end Rand7
Rand5 への 3 回の呼び出し。平均で 125 回のうち 6 回しか繰り返されません。
5x5x5 の 3D 配列で、1 から 7 を繰り返し、6 つの空白を埋めたと考えてください。ブランクを巻き直します。rand5 呼び出しは、その配列に 3 桁の base-5 インデックスを作成します。
4D またはそれ以上の N 次元の配列では、繰り返しは少なくなりますが、これは rand5 関数へのより多くの呼び出しが標準になることを意味します。次元が高くなると、効率が低下し始めます。私には 3 つが適切な妥協案のように思えますが、確実にするためにそれらを相互にテストしていません。そして、それは rand5 実装固有のものになります。
于 2010-10-09T06:47:34.853 に答える
2
これが私が見つけたものです：
- Random5 は 1 ～ 5 の範囲を生成し、ランダムに分散します
- 3回実行してそれらを合計すると、ランダムに分散された3〜15の範囲が得られます
- 3～15の範囲で算術を行う
- (3~15) - 1 = (2~14)
- (2~14)/2 = (1~7)
次に、探している Random7 である 1 ~ 7 の範囲を取得します。
于 2011-08-26T19:10:18.783 に答える
2
これは、他の人の回答を確認した後に作成できる最も簡単な回答です。
def r5tor7():
while True:
cand = (5 * r5()) + r5()
if cand < 27:
return cand
candは [6, 27] の範囲にあり、r5() からの可能な結果が均等に分散されている場合、可能な結果は均等に分散されます。このコードで私の答えをテストできます：
from collections import defaultdict
def r5_outcome(n):
if not n:
yield []
else:
for i in range(1, 6):
for j in r5_outcome(n-1):
yield [i] + j
def test_r7():
d = defaultdict(int)
for x in r5_outcome(2):
s = sum([x[i] * 5**i for i in range(len(x))])
if s < 27:
d[s] += 1
print len(d), d
r5_outcome(2)r5() の結果のすべての可能な組み合わせを生成します。ソリューション コードと同じフィルターを使用してテストします。値が同じであるため、すべての結果が同じ確率であることがわかります。
于 2010-12-01T18:46:59.147 に答える
2
rand(n) -> [0, n - 1]ここでは規約を使用しています
私が読んだ多くの回答から、それらは均一性または停止保証のいずれかを提供しますが、両方ではありません（アダム・ローゼンフェルドの2番目の回答かもしれません）。
ただし、そうすることが可能です。基本的にこの分布があります：
これにより、上の分布に穴[0-6]が残ります。5 と 6 は発生する確率がありません。確率分布をシフトして合計することで穴を埋めようとしていると想像してください。
実際、最初の分布自体を 1 シフトし、得られた分布を 2 シフトした最初の分布と合計し、次に 3 というように、含まれない 7 になるまで繰り返すことができます (範囲全体をカバーしました)。これを次の図に示します。ステップに対応する色の順序は、ブルー -> グリーン -> シアン -> ホワイト -> マゼンタ -> イエロー -> レッドです。
各スロットは 7 つのシフトされた分布 (シフトは 0 から 6 まで変化します) のうちの 5 つによってカバーされ、乱数は
ran5()呼び出しごとに独立していると想定されるため、以下を取得します。
p(x) = 5 / 35 = 1 / 7 for all x in [0, 6]
これは、 からの 7 つの独立した乱数が与えられた場合ran5()、範囲内で一様確率の乱数を計算できることを意味し[0-6]ます。実際、サンプルが独立している限り、ran5() 確率分布は均一である必要さえありません (したがって、分布は試行ごとに同じままです)。また、これは 5 と 7 以外の数字にも有効です。
これにより、次の python 関数が得られます。
def rand_range_transform(rands):
"""
returns a uniform random number in [0, len(rands) - 1]
if all r in rands are independent random numbers from the same uniform distribution
"""
return sum((x + i) for i, x in enumerate(rands)) % len(rands) # a single modulo outside the sum is enough in modulo arithmetic
これは次のように使用できます。
rand5 = lambda : random.randrange(5)
def rand7():
return rand_range_transform([rand5() for _ in range(7)])
rand7()70000 回呼び出すと、次のようになります。
max: 6 min: 0 mean: 2.99711428571 std: 2.00194697049
0: 10019
1: 10016
2: 10071
3: 10044
4: 9775
5: 10042
6: 10033
完璧にはほど遠いですが、これは良いことです。実際のところ、この実装では仮定の 1 つが間違っている可能性が高く、PRNG を使用しているため、次の呼び出しの結果は最後の結果に依存しています。
とはいえ、真にランダムな数値ソースを使用すると、出力も真にランダムになるはずです。そして、このアルゴリズムはすべての場合に終了します。
ただし、これにはコストがかかります。1 回rand5()の呼び出しで7 回の呼び出しが必要rand7()
です。
于 2013-01-31T16:17:33.790 に答える
2
すべてのビットに等しい重みを与えると仮定するrandと、上限でマスクします。
int i = rand(5) ^ (rand(5) & 2);
rand(5)、、、、、のみを返すこと1bが10bでき11bます100b。101b時々 2 ビットを設定することだけに気を配る必要があります。
于 2011-04-04T10:24:33.740 に答える
2
package CareerCup;
public class RangeTransform {
static int counter = (int)(Math.random() * 5 + 1);
private int func() {
return (int) (Math.random() * 5 + 1);
}
private int getMultiplier() {
return counter % 5 + 1;
}
public int rangeTransform() {
counter++;
int count = getMultiplier();
int mult = func() + 5 * count;
System.out.println("Mult is : " + 5 * count);
return (mult) % 7 + 1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RangeTransform rangeTransform = new RangeTransform();
for (int i = 0; i < 35; i++)
System.out.println("Val is : " + rangeTransform.rangeTransform());
}
}
于 2011-01-18T02:42:02.927 に答える
2
このソリューションはエントロピーを無駄にせず、範囲内で最初に利用可能な真の乱数を提供します。反復するたびに、答えが得られない確率が確実に減少します。N 回の反復で答えが得られる確率は、0 から最大 (5^N) までの乱数が、その範囲内の最大の 7 の倍数 (max-max%7) よりも小さくなる確率です。少なくとも 2 回繰り返す必要があります。しかし、それは必然的にすべてのソリューションに当てはまります。
int random7() {
range = 1;
remainder = 0;
while (1) {
remainder = remainder * 5 + random5() - 1;
range = range * 5;
limit = range - (range % 7);
if (remainder < limit) return (remainder % 7) + 1;
remainder = remainder % 7;
range = range % 7;
}
}
数値的には次と同等:
r5=5;
num=random5()-1;
while (1) {
num=num*5+random5()-1;
r5=r5*5;
r7=r5-r5%7;
if (num<r7) return num%7+1;
}
最初のコードはモジュロ形式で計算します。2 番目のコードは単なる数学です。もしくはどこかで間違えた。:-)
于 2014-01-21T07:56:04.340 に答える
2
必要な関数はrand1_7()です。テストしてプロットできるように、 rand1_5() を書きました。
import numpy
def rand1_5():
return numpy.random.randint(5)+1
def rand1_7():
q = 0
for i in xrange(7): q+= rand1_5()
return q%7 + 1
于 2009-12-05T07:27:01.963 に答える
2
なぜこれがうまくいかないのですか？それ以外に、rand5() への 1 つの余分な呼び出しはありますか?
i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14
i = i % 7 + 1;
于 2011-01-27T07:29:38.087 に答える
2
値 0 ～ 7 の場合、次のようになります。
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
ビットごとに左から右へ Rand5() は p(1) = {2/5, 2/5, 3/5} を持ちます。したがって、これらの確率分布 (~Rand5()) を補完すれば、それを使用して数値を生成できるはずです。後で解決策を報告しようと思います。誰にも考えはありますか？
R
于 2011-03-16T17:07:56.140 に答える
1
int rand7()
{
return ( rand5() + (rand5()%3) );
}
- rand5（）-1〜5の値を返します
- rand5（）％3-0から2までの値を返します
- したがって、合計すると、合計値は1〜7の間になります。
于 2012-09-25T15:11:48.920 に答える
1
ここには、一様分布を生成しない多くの解決策があり、それを指摘する多くのコメントがありますが、質問はそれを要件として述べていません。最も簡単な解決策は次のとおりです。
int rand_7() { return rand_5(); }
1〜5の範囲のランダムな整数は、明らかに1〜7の範囲にあります。技術的には、最も簡単な解決策は定数を返すことですが、それは簡単すぎます。
ただし、rand_5関数の存在は赤ニシンだと思います。「1〜7の範囲の整数出力を持つ均一に分散された疑似乱数ジェネレーターを作成する」という質問があったとします。これは単純な問題です（技術的には単純ではありませんが、すでに解決されているので、調べることができます）。
一方、質問が1〜5の範囲の整数（疑似乱数ではない）の真の乱数ジェネレーターを実際に持っていることを意味すると解釈される場合、解決策は次のとおりです。
1) examine the rand_5 function
2) understand how it works
3) profit
于 2013-03-01T00:58:16.053 に答える
1
これはどう
rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2
これが均一に分散されているかどうかはわかりません。助言がありますか？
于 2011-02-18T02:43:45.130 に答える
1
この問題に対する興味深い解決策を考えたので、共有したいと思いました。
function rand7() {
var returnVal = 4;
for (var n=0; n<3; n++) {
var rand = rand5();
if (rand==1||rand==2){
returnVal+=1;
}
else if (rand==3||rand==4) {
returnVal-=1;
}
}
return returnVal;
}
rand7() を 10,000 回ループし、すべての戻り値を合計して 10,000 で割るテスト関数を作成しました。rand7() が正しく機能している場合、計算された平均は 4 になるはずです。たとえば、(1+2+3+4+5+6+7 / 7) = 4 です。複数のテストを実行した後、平均は確かに 4 でした。 :)
于 2011-04-01T02:58:42.147 に答える
1
これが私の一般的な実装です。範囲[0、B-1]のユニフォームジェネレーターが与えられた場合、範囲[0、N-1]のユニフォームを生成します。
public class RandomUnif {
public static final int BASE_NUMBER = 5;
private static Random rand = new Random();
/** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
public static int randomBASE() {
return rand.nextInt(BASE_NUMBER);
}
/** returns uniform integer in the range 0..n-1 using randomBASE() */
public static int randomUnif(int n) {
int rand, factor;
if( n <= 1 ) return 0;
else if( n == BASE_NUMBER ) return randomBASE();
if( n < BASE_NUMBER ) {
factor = BASE_NUMBER / n;
do
rand = randomBASE() / factor;
while(rand >= n);
return rand;
} else {
factor = (n - 1) / BASE_NUMBER + 1;
do {
rand = factor * randomBASE() + randomUnif(factor);
} while(rand >= n);
return rand;
}
}
}
それほど効率的ではありませんが、一般的でコンパクトです。ベースジェネレーターへの平均呼び出し:
n calls
2 1.250
3 1.644
4 1.252
5 1.000
6 3.763
7 3.185
8 2.821
9 2.495
10 2.250
11 3.646
12 3.316
13 3.060
14 2.853
15 2.650
16 2.814
17 2.644
18 2.502
19 2.361
20 2.248
21 2.382
22 2.277
23 2.175
24 2.082
25 2.000
26 5.472
27 5.280
28 5.119
29 4.899
于 2013-01-25T18:54:25.440 に答える
1
Martin's answerに似ていますが、エントロピーを捨てる頻度ははるかに低くなります。
int rand7(void) {
static int m = 1;
static int r = 0;
for (;;) {
while (m <= INT_MAX / 5) {
r = r + m * (rand5() - 1);
m = m * 5;
}
int q = m / 7;
if (r < q * 7) {
int i = r % 7;
r = r / 7;
m = q;
return i + 1;
}
r = r - q * 7;
m = m - q * 7;
}
}
ここでは、 と の間にランダムな値を作成し、0オーバーフローせずに収まる限り多くの状態を追加しm-1て最大化を試みます (これは Cの に収まる最大値です。または、それを意味のある大きな値に置き換えることができます)。あなたの言語とアーキテクチャ)。mINT_MAXint
それで; rが 7 で割り切れる最大の間隔内にある場合、実行可能な結果が含まれ、その間隔を 7 で割り、残りを結果として取り、残りの値をエントロピー プールに返すことができます。それ以外の場合rは、均等に分割されない他の間隔にあり、その適切でない間隔からエントロピー プールを破棄して再起動する必要があります。
ここでの一般的な回答と比較すると、rand5()平均して約半分の頻度で呼び出します。
除算は、パフォーマンスのために単純なビット調整と LUT に分解できます。
于 2015-06-01T06:49:04.900 に答える
1
これは、C++ 11 の機能を利用した回答です。
#include <functional>
#include <iostream>
#include <ostream>
#include <random>
int main()
{
std::random_device rd;
unsigned long seed = rd();
std::cout << "seed = " << seed << std::endl;
std::mt19937 engine(seed);
std::uniform_int_distribution<> dist(1, 5);
auto rand5 = std::bind(dist, engine);
const int n = 20;
for (int i = 0; i != n; ++i)
{
std::cout << rand5() << " ";
}
std::cout << std::endl;
// Use a lambda expression to define rand7
auto rand7 = [&rand5]()->int
{
for (int result = 0; ; result = 0)
{
// Take advantage of the fact that
// 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
// So we only have to discard one out of every 15625 numbers generated.
// Generate a 6-digit number in base 5
for (int i = 0; i != 6; ++i)
{
result = 5 * result + (rand5() - 1);
}
// result is in the range [0, 15625)
if (result == 15625 - 1)
{
// Discard this number
continue;
}
// We now know that result is in the range [0, 15624), a range that can
// be divided evenly into 7 buckets guaranteeing uniformity
result /= 2232;
return 1 + result;
}
};
for (int i = 0; i != n; ++i)
{
std::cout << rand7() << " ";
}
std::cout << std::endl;
return 0;
}
于 2014-09-06T18:16:58.003 に答える
1
皆さんはこれを考えすぎていると思います。この単純な解決策は機能しませんか?
int rand7(void)
{
static int startpos = 0;
startpos = (startpos+5) % (5*7);
return (((startpos + rand5()-1)%7)+1);
}
于 2014-03-28T20:23:59.663 に答える
1
まず頭に浮かんだのはこれです。しかし、それが均一に分布しているかどうかはわかりません。Pythonで実装
インポートランダム
デフrand5（）：
random.randint(1,5) を返す
デフrand7（）：
return ( ( (rand5() -1) * rand5() ) %7 )+1
于 2012-04-30T04:33:37.397 に答える
1
これは @RobMcAfee と似ていますが、2 次元配列の代わりにマジック ナンバーを使用する点が異なります。
int rand7() {
int m = 1203068;
int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;
return (r > 0) ? r : rand7();
}
于 2014-01-06T19:26:12.117 に答える
1
1 から 5 の範囲のランダムな整数を生成する関数が与えられた場合、rand5()1 から 7 の範囲のランダムな整数を生成する関数を書きますrand7()
私が提案したソリューションでは、一rand5度だけ呼び出します
リアルソリューション
float rand7()
{
return (rand5() * 7.0) / 5.0 ;
}
ここでの分布はスケーリングされているため、の分布に直接依存しますrand5
整数解
int rand7()
{
static int prev = 1;
int cur = rand5();
int r = cur * prev; // 1-25
float f = r / 4.0; // 0.25-6.25
f = f - 0.25; // 0-6
f = f + 1.0; // 1-7
prev = cur;
return (int)f;
}
ここでの分布はシリーズによって異なりますrand7(i) ~ rand5(i) * rand5(i-1)
とrand7(0) ~ rand5(0) * 1
于 2014-05-25T10:53:14.580 に答える
0
この問題の主な概念は正規分布に関するものです。ここでは、この問題に対する単純で再帰的な解決策を提供します
rand5()スコープに既にあると仮定します。
def rand7():
# twoway = 0 or 1 in the same probability
twoway = None
while not twoway in (1, 2):
twoway = rand5()
twoway -= 1
ans = rand5() + twoway * 5
return ans if ans in range(1,8) else rand7()
説明
このプログラムを 2 つの部分に分けることができます。
- 1 または 2 が見つかるまで rand5() をループします。つまり、変数に 1 または 2 が含まれる確率は 1/2 です。
twoway - で合成
ansしrand5() + twoway * 5ます。これはまさに の結果ですrand10()。これが必要 (1~7) と一致しない場合は、rand7 を再度実行します。
PS個別にする必要がある可能性があるため、2 番目の部分で while ループを直接実行することはできません。twoway
ただし、最初のセクションの while ループと return ステートメントの再帰のため、この関数は実行時間を保証しないというトレードオフがあり、実際には効果的ではありません。
結果
回答の分布を観察するための簡単なテストを作成しました。
result = [ rand7() for x in xrange(777777) ]
ans = {
1: 0,
2: 0,
3: 0,
4: 0,
5: 0,
6: 0,
7: 0,
}
for i in result:
ans[i] += 1
print ans
それは与えた
{1: 111170, 2: 110693, 3: 110651, 4: 111260, 5: 111197, 6: 111502, 7: 111304}
したがって、この答えは正規分布にあることがわかります。
簡単な答え
この関数の実行時間を気にしない場合は、上記の回答に基づいた簡単な回答を次に示します。
def rand7():
ans = rand5() + (rand5()-1) * 5
return ans if ans < 8 else rand7()
これは、値が 8 より大きい確率を増加させますが、おそらくこの問題に対する最短の答えになるでしょう。
于 2015-04-27T02:38:19.193 に答える
0
これが私のものです。これはMath.random()、複数の関数呼び出しから再作成を試み、「加重分数」(?) で再構築することによってrand5()単位間隔 ( の出力範囲) を再構築します。Math.random()次に、このランダムな単位間隔を使用して、1 から 7 までのランダムな整数を生成します。
function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var uiRandom=0;
var div=1;
for(var i=0; i<7; i++){
div*=5;
var term=(rand5()-1)/div;
uiRandom+=term;
}
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}
言い換えると、0 ～ 4 の間のランダムな整数 (単にrand5()-1) を取り、各結果に 1/5、1/25、1/125、... を掛けてから合計します。これは、バイナリ加重分数がどのように機能するかに似ています。代わりに、これを 5 進数 (基数 5) の加重分数と呼ぶことにします。つまり、0 から 0.999999 までの数値を一連の (1/5)^n 項として生成します。
入力/出力のランダムな整数範囲を取るように関数を変更することは簡単です。上記のコードは、クロージャーとして書き直すと最適化できます。
または、これを行うこともできます。
function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var buffer=[];
var div=1;
for (var i=0; i<7; i++){
buffer.push((rand5()-1).toString(5));
div*=5;
}
var n=parseInt(buffer.join(""),5);
var uiRandom=n/div;
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}
5 進数 (基数 5) の加重分数の作成をいじる代わりに、実際に 5 進数を作成し、それを分数 (前と同様に 0 ～ 0.9999...) に変換してから、ランダムな 1 ～ 7 桁を計算します。そこから。
上記の結果 (コード スニペット #2: それぞれ 100,000 回の呼び出しを 3 回実行):
1: 14263; 2: 14414; 3: 14249; 4: 14109; 5: 14217; 6: 14361; 7:14387
1: 14205; 2: 14394; 3: 14238; 4: 14187; 5: 14384; 6: 14224; 7:14368
1: 14425; 2: 14236; 3: 14334; 4: 14232; 5: 14160; 6: 14320; 7:14293
于 2014-10-23T23:16:39.163 に答える
0
まず、ramdom5() を 1 ポイントで 6 回移動して、7 つの乱数を取得します。2 番目に、7 つの数字を加算して共通の合計を取得します。3 番目に、除算の余りを 7 で取得します。最後に、1 を加算して 1 から 7 までの結果を取得します。この方法では、1 を除いて、1 から 7 までの範囲の数値が得られる確率が等しくなります。1 には少し高い確率。
public int random7(){
Random random = new Random();
//function (1 + random.nextInt(5)) is given
int random1_5 = 1 + random.nextInt(5); // 1,2,3,4,5
int random2_6 = 2 + random.nextInt(5); // 2,3,4,5,6
int random3_7 = 3 + random.nextInt(5); // 3,4,5,6,7
int random4_8 = 4 + random.nextInt(5); // 4,5,6,7,8
int random5_9 = 5 + random.nextInt(5); // 5,6,7,8,9
int random6_10 = 6 + random.nextInt(5); //6,7,8,9,10
int random7_11 = 7 + random.nextInt(5); //7,8,9,10,11
//sumOfRandoms is between 28 and 56
int sumOfRandoms = random1_5 + random2_6 + random3_7 +
random4_8 + random5_9 + random6_10 + random7_11;
//result is number between 0 and 6, and
//equals 0 if sumOfRandoms = 28 or 35 or 42 or 49 or 56 , 5 options
//equals 1 if sumOfRandoms = 29 or 36 or 43 or 50, 4 options
//equals 2 if sumOfRandoms = 30 or 37 or 44 or 51, 4 options
//equals 3 if sumOfRandoms = 31 or 38 or 45 or 52, 4 options
//equals 4 if sumOfRandoms = 32 or 39 or 46 or 53, 4 options
//equals 5 if sumOfRandoms = 33 or 40 or 47 or 54, 4 options
//equals 6 if sumOfRandoms = 34 or 41 or 48 or 55, 4 options
//It means that the probabilities of getting numbers between 0 and 6 are almost equal.
int result = sumOfRandoms % 7;
//we should add 1 to move the interval [0,6] to the interval [1,7]
return 1 + result;
}
于 2014-10-23T22:27:50.013 に答える
0
誰かがこれについてフィードバックをくれるといいのですが、アサート パターンなしで JUNIT を使用しました。これは、Eclipse で簡単かつ迅速に実行できるためです。メイン メソッドを定義することもできます。ちなみに、rand5 は 0 ～ 4 の値を与え、1 を追加すると 1 ～ 5 になり、rand7 と同じであると仮定しています...したがって、議論は解決策について行う必要があります。それは分布であり、0 ～ 4 になるかどうかではありません。または1-5...
package random;
import java.util.Random;
import org.junit.Test;
public class RandomTest {
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}
for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}
public int rand5() {
return new Random().nextInt(5);
}
}
実行すると、次の結果が得られます。
Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037
これは非常に公平な分配のようですね。
rand5() を追加した回数を減らしたり増やしたりすると (回数が 7 で割り切れない場合)、分布は明らかにオフセットを示します。たとえば、rand5()3 回追加します。
Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250
したがって、これは次のようになります。
public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;
}
そして、さらに先に進むことができます：
public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE = 7;
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}
for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;
}
public int rand(int range) {
return new Random().nextInt(range);
}
destRange と originRange をさまざまな値 (ORIGIN の場合は 7、DEST の場合は 13) で置き換えてみたところ、次の分布が得られました。
Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561
ここから結論付けられるのは、起点のランダムな「宛先」時間を合計することで、任意のランダムを別のランダムに変更できるということです。これにより、一種のガウス分布が得られます (中間値がより可能性が高く、エッジ値がより一般的ではありません)。ただし、宛先のモジュラスは、このガウス分布全体に均等に分散しているようです...数学者からのフィードバックがあるとうれしいです...
クールなのは、コストが 100% 予測可能で一定であるのに対し、他のソリューションでは無限ループの可能性がわずかにあることです...
于 2014-10-16T13:14:28.070 に答える
0
簡単な解決策は十分にカバーされています。1 つの結果に対して 2 つのrandom5サンプルを取得random7し、結果が一様分布を生成する範囲外にある場合はやり直します。呼び出しの数を減らすことが目標の場合、これは非常に無駄です。捨てられたサンプルの数により、出力ごとrandom5の呼び出しの平均数は2 ではなく 2.38 になります。random5random7
random5より多くの入力を使用して、一度に複数の出力を生成することで、より良い結果を得ることができますrandom7。31 ビット整数で計算された結果の場合、12 回の呼び出しを使用しrandom5て 9 つの出力を生成するrandom7と、出力ごとに平均 1.34 回の呼び出しが最適になります。244140625 件の結果のうち 2018983 件のみを破棄する必要があるため、効率的です。つまり、1% 未満です。
Python でのデモ:
def random5():
return random.randint(1, 5)
def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break
>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
于 2014-10-15T02:53:52.627 に答える
0
5 で割って 7 を掛けてから、四捨五入しませんか? (確かに、浮動小数点数を使用する必要があります)
他のソリューションよりもはるかに簡単で信頼性が高い (本当に?)。たとえば、Python では次のようになります。
def ranndomNo7():
import random
rand5 = random.randint(4) # Produces range: [0, 4]
rand7 = int(rand5 / 5 * 7) # /5, *7, +0.5 and floor()
return rand7
それは簡単ではありませんでしたか？
于 2012-04-05T20:27:38.047 に答える
0
This algorithm reduces the number of calls of rand5 to the theoretical minimum of 7/5. Calling it 7 times by produce the next 5 rand7 numbers.
There are no rejection of any random bit, and there are NO possibility to keep waiting the result for always.
#!/usr/bin/env ruby
# random integer from 1 to 5
def rand5
STDERR.putc '.'
1 + rand( 5 )
end
@bucket = 0
@bucket_size = 0
# random integer from 1 to 7
def rand7
if @bucket_size == 0
@bucket = 7.times.collect{ |d| rand5 * 5**d }.reduce( &:+ )
@bucket_size = 5
end
next_rand7 = @bucket%7 + 1
@bucket /= 7
@bucket_size -= 1
return next_rand7
end
35.times.each{ putc rand7.to_s }
于 2015-08-11T18:38:48.330 に答える
-1
この複雑な答えを前にして、私はばかげているように感じます。
なぜできないのですか：
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?
于 2009-04-30T17:46:33.007 に答える
-2
ほぼ一様な分布を生成する一定時間の解。トリックは、625 がたまたま 7 できれいに割り切れるということであり、その範囲に達すると均一な分布を得ることができます。
編集：悪いことに、計算を間違えましたが、それを引っ張る代わりに、誰かが役に立つ/面白いと思った場合に備えて残します. 結局のところ、実際には機能します... :)
int rand5()
{
return (rand() % 5) + 1;
}
int rand25()
{
return (5 * (rand5() - 1) + rand5());
}
int rand625()
{
return (25 * (rand25() - 1) + rand25());
}
int rand7()
{
return ((625 * (rand625() - 1) + rand625()) - 1) % 7 + 1;
}
于 2009-04-30T15:14:08.333 に答える
-3
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
于 2009-04-30T17:43:03.920 に答える
-3
#!/usr/bin/env ruby
class Integer
def rand7
rand(6)+1
end
end
def rand5
rand(4)+1
end
x = rand5() # x => int between 1 and 5
y = x.rand7() # y => int between 1 and 7
..それはおそらく不正行為と見なされるかもしれませんが..
于 2009-04-30T17:59:51.837 に答える
-4
PHPでのソリューション
<?php
function random_5(){
return rand(1,5);
}
function random_7(){
$total = 0;
for($i=0;$i<7;$i++){
$total += random_5();
}
return ($total%7)+1;
}
echo random_7();
?>
于 2008-11-27T20:21:43.657 に答える
-4
私は遊んで、この Rand(7) アルゴリズムの「テスト環境」を書きました。たとえば、アルゴリズムにどのような分布が与えられるか、またはすべての異なるランダム値 (Rand(7) 1-7 の場合) を生成するのにどれだけの反復が必要かを試したい場合は、それを使用できます。
私のコアアルゴリズムはこれです：
return (Rand5() + Rand5()) % 7 + 1;
Well は、Adam Rosenfield の井戸よりも均一に分布しています。（スニペットコードに含めました）
private static int Rand7WithRand5()
{
//PUT YOU FAVOURITE ALGORITHM HERE//
//1. Stackoverflow winner
int i;
do
{
i = 5 * (Rand5() - 1) + Rand5(); // i is now uniformly random between 1 and 25
} while (i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;
//My 2 cents
//return (Rand5() + Rand5()) % 7 + 1;
}
この「テスト環境」では、任意の Rand(n) アルゴリズムを使用してテストし、評価できます (分布と速度)。コードを「Rand7WithRand5」メソッドに入れて、スニペットを実行するだけです。
いくつかの観察:
- Adam Rosenfield のアルゴリズムは、たとえば私のアルゴリズムよりも分散されていません。とにかく、両方のアルゴリズムの配布はひどいものです。
- ネイティブ Rand7 (
random.Next(1, 8)) は、約 200 回以上の反復で指定された間隔ですべてのメンバーを生成したときに完了します。Rand7WithRand5 アルゴリズムは 10k (約 30-70k) のオーダーを取ります。 - 実際の課題は、Rand(5) から Rand(7) を生成するメソッドを作成することではなく、多かれ少なかれ均一に分散された値を生成することです。
于 2009-05-03T10:22:05.903 に答える