给定一个生成 1 到 5 范围内的随机整数的函数，编写一个生成 1 到 7 范围内的随机整数的函数。
- 什么是简单的解决方案？
- 什么是减少内存使用或在较慢 CPU 上运行的有效解决方案？
praveen chettypally
问问题
214541 次
77 回答
592
这相当于 Adam Rosenfield 的解决方案，但对某些读者来说可能更清楚一些。它假设 rand5() 是一个函数，它返回一个统计随机整数，范围在 1 到 5 之间（包括 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;
}
它是如何工作的？可以这样想：想象在纸上打印出这个二维阵列，将其钉在飞镖板上，然后随机向其投掷飞镖。如果您遇到一个非零值，它是一个介于 1 和 7 之间的统计随机值，因为可供选择的非零值的数量是相等的。如果您击中零，请继续投掷飞镖，直到击中非零为止。这就是这段代码所做的：i 和 j 索引随机选择飞镖板上的一个位置，如果我们没有得到好的结果，我们会继续投掷飞镖。
就像亚当说的那样，这在最坏的情况下可以永远运行，但从统计学上讲，最坏的情况永远不会发生。:)
于 2009-05-08T22:59:54.800 回答
365
没有（完全正确的）解决方案可以在恒定时间内运行，因为 1/7 是以 5 为底的无限小数。一个简单的解决方案是使用拒绝采样，例如：
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()，以最大化随机性的使用。也就是说，如果您认为随机性是一种宝贵的资源，我们希望尽可能多地使用它，而不会丢弃任何随机位。这个答案也与伊万的答案中提出的逻辑有一些相似之处。
随机变量的熵是一个定义明确的量。对于具有相等概率（均匀分布）的 N 个状态的随机变量，熵为 log 2 N。因此，rand5()具有大约 2.32193 位的熵，并且rand7()具有大约 2.80735 位的熵。如果我们希望最大限度地利用随机性，我们需要使用每次调用的所有 2.32193 位熵rand5()，并将它们应用于生成每次调用所需的 2.80735 位熵rand7()。那么，基本的限制是，我们不能比每次调用 log(7)/log(5) = 1.20906rand5()次调用更好rand7()。
旁注：除非另有说明，否则此答案中的所有对数都将以 2 为底。 rand5()将假定返回范围 [0, 4] 内的数字，rand7()并将假定返回范围 [0, 6] 内的数字。将范围分别调整为 [1, 5] 和 [1, 7] 很简单。
那么我们该怎么做呢？我们生成一个介于 0 和 1 之间的无限精确随机实数（假设我们实际上可以计算和存储这样一个无限精确的数字——我们稍后会解决这个问题）。我们可以通过生成以 5 为底的数字来生成这样的数字：我们选择随机数 0. a1 a2 a3 ...，其中每个数字 ai都是通过调用来选择的rand5()。例如，如果我们的 RNGi为 all 选择 a = 1 i，那么忽略这不是非常随机的事实，这将对应于实数 1/5 + 1/5 2 + 1/5 3 + ... = 1/4（几何级数之和）。
好的，所以我们选择了一个介于 0 和 1 之间的随机实数。我现在声称这样的随机数是均匀分布的。直观地说，这很容易理解，因为每个数字都是统一挑选的，而且数字是无限精确的。然而，对此的正式证明有点复杂，因为现在我们处理的是连续分布而不是离散分布，所以我们需要证明我们的数字位于区间 [ a, b] 中的概率等于那个区间，b - a。证明留给读者练习=）。
现在我们已经从 [0, 1] 范围内均匀选择了一个随机实数，我们需要将其转换为范围 [0, 6] 内的一系列均匀随机数，以生成 的输出rand7()。我们如何做到这一点？与我们刚才所做的相反——我们将其转换为以 7 为底的无限精确小数，然后每个以 7 为底的数字将对应于rand7().
以前面的例子为例，如果我们rand5()产生一个无限的 1 流，那么我们的随机实数将是 1/4。将 1/4 转换为以 7 为底，我们得到无限小数 0.15151515...，因此我们将产生输出 1、5、1、5、1、5 等。
好的，所以我们有了主要的想法，但是我们还有两个问题：我们实际上不能计算或存储一个无限精确的实数，那么我们如何只处理它的有限部分呢？其次，我们如何实际将其转换为 base 7？
我们可以将 0 到 1 之间的数字转换为基数 7 的一种方法如下：
- 乘以 7
- 结果的整数部分是下一个以 7 为基数的数字
- 减去整数部分，只留下小数部分
- 转到第 1 步
为了处理无限精度的问题，我们计算了一个部分结果，并且我们还存储了结果可能是什么的上限。也就是说，假设我们调用rand5()了两次，两次都返回 1。到目前为止，我们生成的数字是 0.11（以 5 为底）。无论产生的无限系列调用的其余部分如何，rand5()我们生成的随机实数永远不会大于 0.12：0.11 ≤ 0.11xyz... < 0.12 总是正确的。
所以，跟踪目前的数字，以及它可以取的最大值，我们将两个数字都转换为以 7 为底。如果它们在第一个k数字上一致，那么我们可以安全地输出下一个k数字——不管是什么以 5 为基数的无限流是，它们永远不会影响以k7 为基数的表示的下一个数字！
这就是算法——为了生成 的下一个输出rand7()，我们只生成rand5()所需的数字，以确保我们确定地知道在随机实数到基数 7 的转换中下一个数字的值。这里是一个 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 算法，在生成大量随机数后，性能将开始显着下降。但请记住，我的目标是最大化随机位的使用，而不是最大化性能（尽管这是次要目标）。
rand5()在其中的一次运行中，我对 10000 次调用进行了 12091 次调用rand7()，实现了 log(7)/log(5) 调用的最小值，平均到 4 个有效数字，并且结果输出是一致的。
为了将此代码移植到没有内置任意大整数的语言，您必须限制本机整数类型的值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，则用 0 填充该位
如果结果是 4 或 5，
如果结果是 3 则用 1 填充该位，然后忽略并再次执行（拒绝）
这样我们可以用 0/1 随机填充 3 位，从而得到一个 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 分之二（假设一个完美的 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 个数量级就会增加一个数量级
顺便说一句：上面的错误表不是通过抽样生成的，而是通过以下递归关系生成的：
p[x,n]是output=x调用.n_rand5
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
下面使用随机数生成器在 {1, 2, 3, 4, 5, 6, 7} 上产生均匀分布，在 {1, 2, 3, 4, 5} 上产生均匀分布。代码乱七八糟，但逻辑清晰。
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 回答
13
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
与选择的解决方案不同，该算法将在恒定时间内运行。然而，它对 rand5 的调用确实比所选解决方案的平均运行时间多 2 次。
请注意，这个生成器并不完美（数字 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 回答
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 回答
12
如果我们考虑尝试给出最有效答案的附加约束，即给出一个输入流 ，I长度m为 1-5 的均匀分布整数输出一个流O，长度为 1-7 的均匀分布整数相对到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=cwherec>0和尽可能小。然后有一个从长度为 m 的输入流到整数 from 1to 的5^m统一映射，以及从整数从 1 到7^n长度为 n 的输出流的另一个统一映射，当映射整数时，我们可能不得不从输入流中丢失一些情况超过7^n。
所以这给出了 的 值L(m)大约m (log5/log7)是.82m。
上述分析的难点在于方程5^m-7^n=c不容易精确求解，以及均匀值 from1超过5^m而7^n失去效率的情况。
问题是可以达到多接近 m (log5/log7) 的最佳值。例如，当这个数字接近整数时，我们能否找到一种方法来实现输出值的精确整数？
如果5^m-7^n=c然后从输入流中，我们有效地从0to生成一个统一的随机数，(5^m)-1并且不使用任何高于7^n. 然而，这些值可以被拯救并再次使用。它们有效地生成从 1 到 的统一数字序列5^m-7^n。因此，我们可以尝试使用这些并将它们转换为 7 进制数，以便我们可以创建更多的输出值。
如果我们让是从大小的统一输入派生的整数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)。
然后整个事情取决于 7 进制数字的分布5^m对于 的各种值m。
我敢肯定有很多理论可以涵盖这一点，我可能会在某个时候查看并报告。
于 2009-05-09T00:11:35.297 回答
10
这是Adam's answer的工作 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 回答
10
为什么不简单呢？
int random7() {
return random5() + (random5() % 3);
}
由于模数，在此解决方案中获得 1 和 7 的机会较低，但是，如果您只想要一个快速且易读的解决方案，这就是要走的路。
于 2009-11-09T12:11:16.173 回答
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
Simple and efficient:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(Inspired by What's your favorite "programmer" cartoon?).
于 2010-08-23T13:14:19.940 回答
6
只要没有七种可能性可供选择，就再画一个随机数，将可能性的数量乘以五。在 Perl 中：
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
于 2009-12-04T23:45:01.020 回答
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
你去了，均匀分布和零 rand5 调用。
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
需要提前播种。
于 2009-12-29T01:46:23.933 回答
5
我知道它已被回答，但这似乎可以正常工作，但我不能告诉你它是否有偏见。我的“测试”表明它至少是合理的。
也许亚当·罗森菲尔德会好心发表评论？
我的（天真？）想法是这样的：
累加 rand5，直到有足够的随机位组成 rand7。这最多需要 2 个 rand5。要获得 rand7 数，我使用累积值 mod 7。
为了避免累加器溢出，并且由于累加器是 mod 7，所以我采用累加器的 mod 7：
(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 亿次试验的结果。
'Real' rand 函数 mod 5 或 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
我的兰德7
平均看起来不错，数字分布看起来也不错。
兰特：平均=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943
于 2010-04-19T12:14:52.647 回答
4
上面引用了一些优雅的算法，但这是一种接近它的方法，尽管它可能是迂回的。我假设从 0 生成的值。
R2 = 给出小于 2 的值的随机数生成器（样本空间 = {0, 1}）
R8 = 给出小于 8 的值的随机数生成器（样本空间 = {0, 1, 2, 3, 4, 5, 6, 7 })
为了从 R2 生成 R8，您将运行 R2 三次，并将所有 3 次运行的组合结果用作具有 3 位数字的二进制数。以下是 R2 运行三次时的值范围：
0 0 0 --> 0
。
.
1 1 1 --> 7
现在要从 R8 生成 R7，如果返回 7，我们只需再次运行 R7：
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..4} 中使用 1.26 个随机数来对 {0..6} 中的每个随机数）。代码在 Scala 中，但任何语言的数学运算都应该相当清楚：您可以利用 7^9 + 7^8 非常接近 5^11 的事实。所以你选择一个以 5 为底的 11 位数字，然后如果它在范围内（给出 9 个以 7 为底的数字），则将其解释为以 7 为底的 9 位数字，或者如果它超过 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
分布很好且平坦（在每个 bin 中 10^8 的 1/7 的大约 10k 范围内，正如近似高斯分布所预期的那样）。
于 2010-03-10T21:25:58.103 回答
3
通过使用滚动总计，您可以同时
- 保持平均分配；和
- 不必牺牲随机序列中的任何元素。
这两个问题都是简单rand(5)+rand(5)...型解决方案的问题。以下 Python 代码显示了如何实现它（其中大部分是证明分布）。
import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
##### qq.py #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
##### qq_notsogood.py #####
#r = 20
#while r > 6:
#r = int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)
这个输出显示了结果：
pax$ python qq.py
0: 99908 14.27257
1: 100029 14.28986
2: 100327 14.33243
3: 100395 14.34214
4: 99104 14.15771
5: 99829 14.26129
6: 100408 14.34400
Variation = 1304 (0.18629%)
pax$ python qq.py
0: 99547 14.22100
1: 100229 14.31843
2: 100078 14.29686
3: 99451 14.20729
4: 100284 14.32629
5: 100038 14.29114
6: 100373 14.33900
Variation = 922 (0.13171%)
pax$ python qq.py
0: 100481 14.35443
1: 99188 14.16971
2: 100284 14.32629
3: 100222 14.31743
4: 99960 14.28000
5: 99426 14.20371
6: 100439 14.34843
Variation = 1293 (0.18471%)
一个简单的rand(5)+rand(5)，忽略返回超过 6 的那些情况，其典型变化为 18%，是上面显示的方法的100 倍：
pax$ python qq_notsogood.py
0: 31756 4.53657
1: 63304 9.04343
2: 95507 13.64386
3: 127825 18.26071
4: 158851 22.69300
5: 127567 18.22386
6: 95190 13.59857
Variation = 127095 (18.15643%)
pax$ python qq_notsogood.py
0: 31792 4.54171
1: 63637 9.09100
2: 95641 13.66300
3: 127627 18.23243
4: 158751 22.67871
5: 126782 18.11171
6: 95770 13.68143
Variation = 126959 (18.13700%)
pax$ python qq_notsogood.py
0: 31955 4.56500
1: 63485 9.06929
2: 94849 13.54986
3: 127737 18.24814
4: 159687 22.81243
5: 127391 18.19871
6: 94896 13.55657
Variation = 127732 (18.24743%)
而且，根据 Nixuz 的建议，我已经清理了脚本，以便您可以提取和使用这些rand7...内容：
import random
# rand5() returns 0 through 4 inclusive.
def rand5():
return int (random.random () * 5)
# rand7() generator returns 0 through 6 inclusive (using rand5()).
def rand7():
rand7ret = 0
while True:
rand7ret = (rand7ret + rand5()) % 7
yield rand7ret
# Number of test runs.
count = 700000
# Work out distribution.
distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
r = rgen.next()
distrib[r] = distrib[r] + 1
# Print distributions and calculate variation.
high = distrib[0]
low = distrib[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
if distrib[i] < low:
low = distrib[i]
if distrib[i] > high:
high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
于 2009-05-07T03:43:40.400 回答
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 的比率为 2.125 次调用 Rand5。最佳值应为 2.1。
我想这种方法比这里的许多其他方法要慢得多，除非调用 Rand5 的成本非常昂贵（比如调用一些外部熵源）。
于 2009-05-13T17:38:16.923 回答
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 回答
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 之间的浮点数，然后向下舍入以得到 1 到 7 之间的 int。如果我没记错的话，有 16/112 的机会得到7 个结果中的任何一个。
于 2011-04-01T04:06:43.740 回答
3
extern int r5();
int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
于 2010-12-03T01:31:46.060 回答
3
我想我有四个答案，其中两个给出了与@Adam Rosenfield 类似的精确解决方案，但没有无限循环问题，另外两个给出了几乎完美的解决方案，但比第一个解决方案更快。
最好的精确解决方案需要 7 次调用rand5，但让我们继续了解。
方法 1 - 精确
亚当的答案的优势在于它给出了一个完美的均匀分布，并且很有可能（21/25）只需要两次调用 rand5() 。然而，最坏的情况是无限循环。
下面的第一个解决方案也提供了完美的均匀分布，但总共需要 42 次调用rand5. 没有无限循环。
这是一个 R 实现：
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1
对于不熟悉 R 的人，这里有一个简化的版本：
rand7 = function(){
r = 0
for(i in 0:6){
r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
}
return r %% 7 + 1
}
的分布rand5将被保留。如果我们进行数学计算，循环的 7 次迭代中的每一次都有 5^6 种可能的组合，因此可能的组合总数为(7 * 5^6) %% 7 = 0. 因此，我们可以将生成的随机数分成 7 个相等的组。有关此问题的更多讨论，请参见方法二。
以下是所有可能的组合：
table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
15625 15625 15625 15625 15625 15625 15625
我认为直接表明亚当的方法会运行得更快。在 Adam 的解决方案中有 42 次或更多调用的概率rand5非常小 ( (4/25)^21 ~ 10^(-17))。
方法 2 - 不准确
现在第二种方法几乎是统一的，但需要 6 次调用rand5：
rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
这是一个简化版本：
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return r %% 7 + 1
}
这本质上是方法 1 的一次迭代。如果我们生成所有可能的组合，则结果计数如下：
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
2233 2232 2232 2232 2232 2232 2232
5^6 = 15625一个数字将在试验中再次出现。
现在，在方法 1 中，通过将 1 加到 6，我们将数字 2233 移动到每个连续点。因此，组合的总数将匹配。这是因为 5^6 %% 7 = 1，然后我们做了 7 个适当的变化，所以 (7 * 5^6 %% 7 = 0)。
方法 3 - 精确
如果理解方法 1 和 2 的参数，则方法 3 随之而来，并且只需要 7 次调用rand5. 在这一点上，我觉得这是精确解决方案所需的最少调用次数。
这是一个 R 实现：
rand5 <- function() sample(1:5,1)
rand7 <- function() (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1
对于不熟悉 R 的人，这里有一个简化的版本：
rand7 = function(){
r = 0
for(i in 1:7){
r = r + i * rand5()
}
return r %% 7 + 1
}
的分布rand5将被保留。如果我们进行数学计算，循环的 7 次迭代中的每一次都有 5 种可能的结果，因此可能的组合总数为(7 * 5) %% 7 = 0. 因此，我们可以将生成的随机数分成 7 个相等的组。有关此问题的更多讨论，请参见方法一和方法二。
以下是所有可能的组合：
table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
5 5 5 5 5 5 5
我认为直接表明亚当的方法仍然会运行得更快。在 Adam 的解决方案中有 7 个或更多调用的概率rand5仍然很小 ( (4/25)^3 ~ 0.004)。
方法 4 - 不准确
这是第二种方法的微小变化。它几乎是统一的，但需要 7 次调用rand5，这是方法 2 的额外调用：
rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1
这是一个简化版本：
rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return (r+rand5()) %% 7 + 1
}
如果我们生成所有可能的组合，则结果计数如下：
table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)
1 2 3 4 5 6 7
11160 11161 11161 11161 11161 11161 11160
5^7 = 78125两个数字将在试验中少出现一次。对于大多数目的，我可以忍受。
于 2017-12-02T00:29:46.990 回答
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
我们在rand(n) -> [0, n - 1]这里使用约定
从我阅读的许多答案中，它们提供了一致性或停止保证，但不能同时提供（亚当·罗森菲尔德的第二个答案可能）。
但是，可以这样做。我们基本上有这个分布：
这给我们的分布留下了一个漏洞[0-6]： 5 和 6 没有发生的概率。想象一下，现在我们试图通过改变概率分布和求和来填补它的漏洞。
实际上，我们可以将初始分布本身移动一，然后通过将获得的分布与初始一移动二，然后三，依此类推，直到 7，不包括在内（我们覆盖了整个范围）。如下图所示。颜色的顺序，对应于步骤，是蓝色 -> 绿色 -> 青色 -> 白色 -> 品红色 -> 黄色 -> 红色。
因为每个槽被 7 个移位分布中的 5 个覆盖（移位从 0 到 6 不等），并且因为我们假设随机数独立于
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
这很好，虽然远非完美。事实是，在这个实现中，我们的一个假设很可能是错误的：我们使用 PRNG，因此，下一次调用的结果取决于最后一个结果。
也就是说，使用真正随机的数字源，输出也应该是真正随机的。这个算法在任何情况下都会终止。
但这是有代价的：一次调用需要 7rand5()次rand7()
调用。
于 2013-01-31T16:17:33.790 回答
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 回答
2
该解决方案不会浪费任何熵，并给出范围内第一个可用的真正随机数。随着每次迭代，没有得到答案的概率被证明是降低了。在 N 次迭代中得到答案的概率是介于 0 和 max (5^N) 之间的随机数将小于该范围内最大的 7 倍数 (max-max%7) 的概率。必须至少迭代两次。但这对于所有解决方案都是如此。
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;
}
第一个代码以模数形式计算它。第二个代码只是简单的数学。或者我在某个地方犯了一个错误。:-)
于 2014-01-21T07:56:04.340 回答
2
这是我发现的：
- Random5 产生一个 1~5 的范围，随机分布
- 如果我们运行 3 次并将它们相加，我们将得到 3~15 的范围，随机分布
- 对 3~15 范围进行算术运算
- (3~15) - 1 = (2~14)
- (2~14)/2 = (1~7)
然后我们得到一个1~7的范围，也就是我们要找的Random7。
于 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
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
为什么这行不通？除了对 rand5() 的一次额外调用之外？
i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14
i = i % 7 + 1;
于 2011-01-27T07:29:38.087 回答
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 次。
把它想象成一个 3D 数组，5x5x5，一遍又一遍地填充 1 到 7 个，以及 6 个空白。在空白处重新滚动。rand5 调用在该数组中创建了一个三位数的 base-5 索引。
4D 或更高的 N 维数组的重复次数会更少，但这意味着对 rand5 函数的更多调用成为标准。您将开始在更高维度上获得递减的效率回报。在我看来，三个是一个很好的折衷方案，但我还没有对它们进行过测试以确定。这将是特定于 rand5 实现的。
于 2010-10-09T06:47:34.853 回答
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
假设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
此处似乎未涵盖的另一个答案：
int rand7() {
int r = 7 / 2;
for (int i = 0; i < 28; i++)
r = ((rand5() - 1) * 7 + r) / 5;
return r + 1;
}
每次迭代r都有一个介于 0 和 6 之间的随机值（包括 0 和 6）。将其附加（以 7 为基数）到 0 到 4（含）之间的随机值，结果除以 5，给出 0 到 6（含）范围内的新随机值。 r从一个很大的偏差开始（r = 3非常有偏差！），但每次迭代都会将该偏差除以 5。
这种方法并不完全统一；但是，偏差非常小。大约 1/(2**64) 的东西。这种方法的重要之处在于它具有恒定的执行时间（假设rand5()也具有恒定的执行时间）。没有理论上的担忧，即不幸的调用可能会永远迭代选择错误的值。
此外，一个很好的措施的讽刺答案（有意或无意，它已被涵盖）：
1-5 已经在 1-7 范围内，因此以下是有效的实现：
int rand7() {
return rand5();
}
问题没有要求均匀分布。
于 2015-06-01T08:53:49.413 回答
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 回答
1
此解决方案的灵感来自 Rob McAfee。
但是它不需要循环，结果是均匀分布：
// Returns 1-5
var rnd5 = function(){
return parseInt(Math.random() * 5, 10) + 1;
}
// Helper
var lastEdge = 0;
// Returns 1-7
var rnd7 = function () {
var map = [
[ 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 ]
];
var result = map[rnd5() - 1][rnd5() - 1];
if (result > 0) {
return result;
}
lastEdge++;
if (lastEdge > 7 ) {
lastEdge = 1;
}
return lastEdge;
};
// Test the a uniform distribution
results = {}; for(i=0; i < 700000;i++) { var rand = rnd7(); results[rand] = results[rand] ? results[rand] + 1 : 1;}
console.log(results)
结果：[1: 99560, 2: 99932, 3: 100355, 4: 100262, 5: 99603, 6: 100062, 7: 100226]
于 2014-03-17T23:50:29.523 回答
1
这与@RobMcAfee 类似，只是我使用幻数而不是二维数组。
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
我想你们都想多了。这个简单的解决方案不起作用吗？
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
这个怎么样
rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2+rand5()%2
不确定这是均匀分布的。有什么建议么？
于 2011-02-18T02:43:45.130 回答
1
function rand7() {
while (true) { //lowest base 5 random number > 7 reduces memory
int num = (rand5()-1)*5 + rand5()-1;
if (num < 21) // improves performance
return 1 + num%7;
}
}
Python代码：
from random import randint
def rand7():
while(True):
num = (randint(1, 5)-1)*5 + randint(1, 5)-1
if num < 21:
return 1 + num%7
100000 次运行的测试分布：
>>> rnums = []
>>> for _ in range(100000):
rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}
于 2013-12-18T21:17:55.523 回答
1
我首先想到的是这个。但我不知道它是否均匀分布。在python中实现
随机导入
def rand5():
返回随机数.randint(1,5)
def rand7():
返回 ( ( (rand5() -1) * rand5() ) %7 )+1
于 2012-04-30T04:33:37.397 回答
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
这里有很多解决方案不会产生均匀分布，许多评论指出了这一点，但问题并未将其作为要求。最简单的解决方案是：
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
int rand7()
{
return ( rand5() + (rand5()%3) );
}
- rand5() - 返回 1-5 的值
- rand5()%3 - 返回 0-2 的值
- 所以，当总结总价值将在 1-7 之间
于 2012-09-25T15:11:48.920 回答
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
这是利用 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
与Martin 的回答类似，但不太频繁地使用熵：
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，并尝试m通过添加尽可能多的状态来最大化而不会溢出（INT_MAX这是适合int在 C 中的最大值，或者您可以用任何有意义的大值替换它你的语言和架构）。
然后; 如果r落在可被 7 整除的最大可能区间内，则它包含一个可行的结果，我们可以将该区间除以 7，并将余数作为我们的结果，并将剩余的值返回到我们的熵池。否则r在另一个不均匀划分的区间中，我们必须从那个不合适的区间丢弃并重新启动我们的熵池。
与这里的流行答案相比，它的调用rand5()频率平均约为一半。
可以将这些划分分解为琐碎的位旋转和 LUT 以提高性能。
于 2015-06-01T06:49:04.900 回答
1
来自扩大浮动范围的链接。这个更好玩。我没有得出结论，而是想到对于给定的f具有“基数” b的随机整数生成函数（在这种情况下为 4，我将说明原因），它可以扩展如下：
(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)
这会将随机生成器转换为 FLOAT 生成器。我将在这里定义 2 个参数b和p. 虽然这里的“基数”是 4，但 b 实际上可以是任何东西，也可以是无理数等p，我称精度是您希望浮点生成器的粒度程度。将此视为rand5每次调用rand7.
但我意识到如果你将 b 设置为 base+1（在这种情况下为 4+1 = 5），这是一个最佳点，你会得到一个均匀的分布。首先摆脱这个 1-5 生成器，实际上是 rand4() + 1：
function rand4(){
return Math.random() * 5 | 0;
}
要到达那里，你可以rand4用rand5()-1
接下来是将rand4从整数生成器转换为浮点生成器
function toFloat(f,b,p){
b = b || 2;
p = p || 3;
return (Array.apply(null,Array(p))
.map(function(d,i){return f()})
.map(function(d,i){return Math.pow(b,i)*d})
.reduce(function(ac,d,i){return ac += d;}))
/
(
(Math.pow(b,p) - 1)
/(b-1)
)
}
这会将我编写的第一个函数应用于给定的 rand 函数。试试看：
toFloat(rand4) //1.4285714285714286 base = 2, precision = 3
toFloat(rand4,3,4) //0.75 base = 3, precision = 4
toFloat(rand4,4,5) //3.7507331378299122 base = 4, precision = 5
toFloat(rand4,5,6) //0.2012288786482335 base = 5, precision =6
...
现在您可以将此浮点范围（0-4 INCLUSIVE）转换为任何其他浮点范围，然后将其降级为整数。这里我们的基础是4因为我们正在处理rand4，因此一个值b=5会给你一个均匀的分布。随着 b 增长超过 4，您将开始在分布中引入周期性间隙。我测试了从 2 到 8 的 b 值，每个值 3000 分，并与 JavaScript 的原生 Math.random 进行比较，在我看来甚至比原生的更好：
http://jsfiddle.net/ibowankenobi/r57v432t/
对于上面的链接，单击分布顶部的“bin”按钮以减小分箱大小。最后一张图是原生 Math.random，第 4 个 d=5 是统一的。
得到浮点范围后，要么乘以 7 并抛出小数部分，要么乘以 7，减去 0.5 并四舍五入：
((toFloat(rand4,5,6)/4 * 7) | 0) + 1 ---> occasionally you'll get 8 with 1/4^6 probability.
Math.round((toFloat(rand4,5,6)/4 * 7) - 0.5) + 1 --> between 1 and 7
于 2018-09-10T08:07:30.660 回答
1
- 什么是简单的解决方案？
(rand5() + rand5()) % 7 + 1 - 什么是减少内存使用或在较慢 CPU 上运行的有效解决方案？
Yes, this is effective as it calls rand5() only twice and have O(1) space complexity
考虑rand5()给出从 1 到 5（含）的随机数。
(1 + 1) % 7 + 1 = 3
(1 + 2) % 7 + 1 = 4
(1 + 3) % 7 + 1 = 5
(1 + 4) % 7 + 1 = 6
(1 + 5) % 7 + 1 = 7
(2 + 1) % 7 + 1 = 4
(2 + 2) % 7 + 1 = 5
(2 + 3) % 7 + 1 = 6
(2 + 4) % 7 + 1 = 7
(2 + 5) % 7 + 1 = 1
...
(5 + 1) % 7 + 1 = 7
(5 + 2) % 7 + 1 = 1
(5 + 3) % 7 + 1 = 2
(5 + 4) % 7 + 1 = 3
(5 + 5) % 7 + 1 = 4
...
等等
于 2017-04-01T19:30:02.260 回答
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()
解释
我们可以把这个程序分成两部分：
- 循环 rand5() 直到我们找到 1 或 2，这意味着我们有 1/2 的概率在变量中有 1 或 2
twoway ans由合成rand5() + twoway * 5，这正是 的结果rand10()，如果这不符合我们的需要（1~7），那么我们再次运行 rand7。
PS 我们不能在第二部分直接运行一个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 为底）加权分数：从 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;
}
我们实际上将创建一个五进制数并将其转换为分数（0--0.9999... 和以前一样），而不是摆弄构造一个五进制（以 5 为底）加权分数，然后计算我们的随机 1--7 位从那里。
上述结果（代码片段 #2：3 次运行，每次调用 100,000 次）：
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
这个表达式足以得到 1 - 7 之间的随机整数
int j = ( rand5()*2 + 4 ) % 7 + 1;
于 2013-09-02T12:34:23.560 回答
0
如果有人能给我关于这个的反馈会很酷，我使用了没有断言模式的 JUNIT，因为在 Eclipse 中运行它既容易又快速，我也可以定义一个 main 方法。顺便说一句，我假设 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
为什么不直接除以 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
首先，我在 1 点上移动 ramdom5() 6 次，得到 7 个随机数。其次，我将 7 个数字相加以获得共同的和。第三，我在 7 处得到除法的余数。最后，我加 1 得到从 1 到 7 的结果。这种方法给出了得到 1 到 7 范围内数字的相等概率，但 1 除外。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
简单的解决方案已经很好地涵盖了：random5为一个结果取两个样本，random7如果结果超出生成均匀分布的范围，则重新进行。如果您的目标是减少调用次数，random5这是非常浪费的 -由于丢弃样本的数量，random5每个输出的平均调用次数为 2.38 而不是 2。random7
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
对于 [1, 5] 到 [1, 7] 的范围，这相当于用 5 面骰子滚动 7 面骰子。
但是，如果不“浪费”随机性（或者在最坏的情况下永远运行），这是无法做到的，因为 7 的所有质因数（即 7）不整除 5。因此，可以做到的最好的就是使用拒绝抽样来任意接近没有“浪费”的随机性（例如通过批量处理多卷 5 面模具，直到 5^ n “足够接近”到 7 的幂）。这个问题的解决方案已经在其他答案中给出。
更一般地说，用p面骰子掷k面骰子的算法将不可避免地“浪费”随机性（并且在最坏的情况下永远运行），除非“每个除k的素数也除p ”，根据引理 3 在B. Kloeckner 的“用骰子模拟骰子”。例如，采用更实际的情况，即p是 2 的幂，k是任意的。在这种情况下，这种“浪费”和不确定的运行时间是不可避免的，除非k也是 2 的幂。
于 2020-08-31T23:24:44.173 回答
0
这是一个解决方案，它试图最小化对 rand5() 的调用次数，同时保持实现简单高效；特别是，它不像 Adam Rosenfield 的第二个答案那样需要任意大整数。它利用了 23/19 = 1.21052... 是 log(7)/log(5) = 1.20906... 的良好有理逼近这一事实，因此我们可以生成 {1,...,7 的 19 个随机元素} 在 {1,...,5} 的 23 个随机元素中，通过仅以很小的拒绝概率进行拒绝采样。平均而言，对于 rand7() 的每次调用，下面的算法大约需要 1.266 次对 rand5() 的调用。如果 rand5() 的分布是均匀的，那么 rand7() 也是均匀的。
uint_fast64_t pool;
int capacity = 0;
void new_batch (void)
{
uint_fast64_t r;
int i;
do {
r = 0;
for (i = 0; i < 23; i++)
r = 5 * r + (rand5() - 1);
} while (r >= 11398895185373143ULL); /* 7**19, a bit less than 5**23 */
pool = r;
capacity = 19;
}
int rand7 (void)
{
int r;
if (capacity == 0)
new_batch();
r = pool % 7;
pool /= 7;
capacity--;
return r + 1;
}
于 2019-08-27T15:01:55.207 回答
0
该算法将 rand5 的调用次数减少到理论最小值的 7/5。通过产生接下来的 5 个 rand7 数字来调用它 7 次。
没有拒绝任何随机位，也不可能一直等待结果。
#!/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 回答
-2
def rand5():
return random.randint(1,5) #return random integers from 1 to 5
def rand7():
rand = rand5()+rand5()-1
if rand > 7: #if numbers > 7, call rand7() again
return rand7()
print rand%7 + 1
我想这将是最简单的解决方案，但是人们5*rand5() + rand5() - 5在http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/中提出的建议。有人可以解释有什么问题吗rand5()+rand5()-1
于 2015-05-12T11:17:59.930 回答
-2
// returns random number between 0-5 with equal probability
function rand5() {
return Math.floor(Math.random() * 6);
}
// returns random number between 0-7 with equal probability
function rand7() {
if(rand5() % 2 == 0 && rand5() % 2 == 0) {
return 6 + rand5() % 2;
} else {
return rand5();
}
}
console.log(rand7());于 2019-05-17T10:49:45.047 回答
-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
..although that may possibly be considered cheating..
于 2009-04-30T17:59:51.837 回答
-3
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
于 2009-04-30T17:43:03.920 回答
-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 的算法的分布并不比我的算法好。无论如何，这两种算法的分布都很糟糕。
- Native Rand7 (
random.Next(1, 8)) 在大约 200 多次迭代中生成给定间隔内的所有成员时完成，Rand7WithRand5 算法需要 10k（大约 30-70k） - 真正的挑战不是编写从 Rand(5) 生成 Rand(7) 的方法，而是生成或多或少均匀分布的值。
于 2009-05-03T10:22:05.903 回答
-4
这是我想出的答案，但这些复杂的答案让我觉得这完全不对/:))
import random
def rand5():
return float(random.randint(0,5))
def rand7():
random_val = rand5()
return float(random.randint((random_val-random_val),7))
print rand7()
于 2018-08-24T01:43:12.287 回答