给定一个生成范围在1到5之间随机整数的函数，编写一个生成范围在1到7之间随机整数的函数。
78个回答
600
这与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索引随机选择飞镖板上的一个位置，如果我们没有得到一个好的结果，我们就继续投掷飞镖。
就像Adam所说，最坏情况下它可能永远运行下去，但从统计角度来看，最坏情况永远不会发生:)
- Rob McAfee
25
8我理解这个解决方案背后的逻辑，但不明白它是如何导致均匀概率的。有人能解释一下其中的数学吗？ - user1071840
7如果
rand5是均匀的，那么vals网格中的每个单元格被选中的概率相等。该网格恰好包含区间[1,7]中每个整数的三个副本，以及四个零。因此，“原始”的结果流趋向于均匀混合的[1,7]值，再加上一些比任何单个允许值更频繁出现的零。但这不重要，因为零被去除了，只留下均匀混合的[1,7]值。 - Daniel Earwicker4快速了解这个问题的方法是：如果您只调用rand5()一次，则只有5种可能的结果。显然，除非添加更多的随机性，否则无法将其转换为超过5种可能的结果。 - Daniel Earwicker
3rand5()函数只能生成(1, 2, 3, 4, 5)这五个数值中的一个。因此，rand5()*5生成的结果也只能是(5, 10, 15, 20, 25)这五个数值中的一个，而不是完整的范围(1...25)。如果它是完整的范围，那么减去4就会变成(-3...21)，但在这种情况下，它变成了(1, 6, 11, 16, 21)，因此端点是正确的，但有四个大的空洞：(2..5)，(7..10)，(12..15)，(17..21)。最后进行mod 7并加上1，得到(2, 7, 5, 3, 1)。因此，4和6都不可能出现。但是（请参见上面的快捷方式），我们一直知道生成的范围中只能有5个数字，所以必须有两个空缺。 - Daniel Earwicker
2你把零放在末尾有什么原因吗？ - TheOne
显示剩余20条评论
369
由于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次迭代，但是有无限小的可能会一直循环下去。
- Adam Rosenfield
41
7如果将>21翻转为>26，则无需-1，因为i的下限映射到哪里并不重要。 - BCS
26我认为这是正确的原因：假设我想编写一个程序，输出1到25之间的均匀随机数流；对于这个问题，我可以使用代码中的方法，返回5 * (rand5() - 1) + rand5()。现在，如果我想要生成1到21之间的均匀随机数流，我可以使用第一个随机数流，但要过滤掉[22, 25]范围内的数字。接下来，如果我将这个流过滤一遍，使得每个元素都变成x % 7 + 1，那么我就得到了一个1到7之间的均匀随机数流！相当简单吧？:D - Paggas
7你说得对，问题在于你是否愿意选择完美的分布但运行时间无限制，或不完美的分布但运行时间有上限。这是因为如果所有5的次方数都不能被7整除，或者等价地，如果你有5的n次方个等可能的长度为n的序列，就没有办法将1到7之间的每个数字分配给每个序列，使得1到7每个数字出现的概率相等。 - Adam Rosenfield
5假设存在一个在最坏情况下保证调用
rand5()不超过N次且运行时间为常数的解决方案。那么，对于每个1≤k≤7的输出，将所有可能的调用序列的输出为“k”的概率相加，得到输出为“k”的概率是m/5^N，其中m是这样的序列数量。因此，m/5^N = 1/7，但是没有可能的整数解(N,m)满足此等式==>矛盾。 - Adam Rosenfield4@paxdiablo：您是错误的。真随机数发生器生成无限长的“5”的概率恰好为0，使用类似于 抛硬币无限次不可能产生无限连续正面的概率 的推理即可得出这一结论。这也意味着这段代码永远不会进入无限循环（尽管有正的概率它会循环任意多次）。 - BlueRaja - Danny Pflughoeft
显示剩余36条评论
154
除了我的第一个答案，我还想再添加一个答案。这个答案试图最小化对于每次调用rand7()需要调用rand5()的次数，以最大化随机性的使用。也就是说，如果您认为随机性是一种宝贵的资源，我们希望尽可能地使用它，而不会浪费任何随机位。这个答案也与Ivan的答案中提出的逻辑有一些相似之处。
随机变量的熵是一个定义明确的量。对于一个等概率（即均匀分布）取N种状态的随机变量，其熵为log2 N。因此，rand5()大约具有2.32193比特的熵，而rand7()大约具有2.80735比特的熵。如果我们希望最大化随机性的使用，我们需要使用每次调用rand5()返回的全部2.32193比特熵，并将它们应用于生成每次调用rand7()所需的2.80735比特熵。那么，基本限制就是我们最多只能进行log(7)/log(5) = 1.20906次rand5()调用来生成一次rand7()调用。
附注：本答案中所有对数都以2为底，除非另有说明。rand5()被假定返回范围在[0,4]的数字，而rand7()则被假定返回范围在[0,6]的数字。将范围调整到分别为[1,5]和[1,7]是微不足道的。
那么我们该怎么做呢？ 我们生成一个0到1之间的无限精确随机实数（暂时假设我们可以实际计算和存储这样一个无限精确的数字--我们稍后会解决这个问题）。我们可以通过在基数为5时生成其数字来生成这样的数字：我们选择随机数0。a1a2a3...，其中每个数字ai都是通过调用rand5()来选择的。例如，如果我们的RNG对所有i都选择ai = 1，那么忽略它不太随机的事实，那将对应于实数1/5 + 1/52 + 1/53 + ... = 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等。
好了，我们有了主要思路，但还有两个问题：我们实际上无法计算或存储无限精确实数，那么我们如何处理它的有限部分？其次，我们实际上如何将其转换为基数为7的数字呢？
我们可以将0到1之间的数字转换为基数为7的数字的一种方法如下：
- 将数字乘以7
- 取结果的整数部分作为下一个七进制位
- 减去整数部分，只保留小数部分
- 回到步骤1
为了解决精度无限的问题，我们计算一个部分结果，并存储一个可能的上限。也就是说，假设我们两次调用rand5()并且都返回了1，那么我们生成的数字是0.11（五进制）。无论后续对rand5()的无限次调用生成什么，我们生成的随机实数永远不会大于0.12：始终成立0.11 ≤ 0.11xyz... < 0.12。
因此，我们跟踪当前的数字和它可能达到的最大值，然后将这两个数都转换为七进制。如果它们在前面的k位相同，则我们可以安全地输出下一个k位 -- 不管基于五进制的无限流产生什么，它们永远不会影响到七进制表示法中下一个k位的值！
这就是算法 -- 要生成下一个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() 返回一个生成器，因为它具有内部状态，涉及将数字转换为七进制。测试框架调用 next(r7) 10000 次以产生 10000 个随机数，然后测量它们的分布。仅使用整数运算，因此结果是完全正确的。
还要注意，这里的数字会非常快地变得非常大。5 和 7 的幂增长很快。因此，在生成大量随机数后，由于 bignum 算术，性能将开始明显下降。但请记住，我的目标是最大化使用随机比特位，而不是最大化性能（尽管这是次要目标）。
在一次运行中，我对 rand7() 进行了 10000 次调用，对 rand5() 进行了 12091 次调用，平均每次调用需要调用 log(7)/log(5) 次，精确到 4 个有效数字，并且生成的输出是均匀分布的。
为了将此代码移植到没有内置任意大整数的语言中，您必须将 pow5 和 pow7 的值限制为本机整数类型的最大值——如果它们变得太大，则重置所有内容并重新开始。这将稍微增加每次调用 rand7() 对 rand5() 的平均调用次数，但希望即使对于 32 或 64 位整数，它也不会增加太多。
- Adam Rosenfield
8
7非常有趣的答案，点赞！是否可能不是在特定值处重置，而是将已使用的位移除并移动其他位，并基本上只保留将要使用的位？或者我漏掉了什么吗？ - Chris Lutz
1我不是100%确定，但我相信如果你这样做，你会稍微扭曲分布（尽管我怀疑在没有进行数万亿次试验的情况下，这种扭曲是无法测量的）。 - Adam Rosenfield
2非常好！我们能在不增加状态的情况下保留额外的熵吗？诀窍是注意到上限和下限始终是有理数。我们可以进行加法、减法和乘法，而不会失去精度。如果我们全部使用35进制来完成，我们就接近成功了。剩下的部分（乘以七并保留小数部分）留作练习。 - Ian
这是非常好的答案，也是我最喜欢的答案。它还具有有限的运行时间。 - Isaac
1@Isaac：不，这个算法没有有界的运行时间。任何准确的答案都不能有有界的运行时间。 - Adam Rosenfield
显示剩余3条评论
37
（我抄袭了 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);
}
编辑：在此方程式中，预计调用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()
- Eyal
4
2在100万次尝试中记录的结果：1=47216；2=127444；3=141407；4=221453；5=127479；6=167536；7=167465。正如您所看到的，与获得1的概率相比，分布不足。 - Robert K
2@The Wicked Flea：我认为你弄错了。你确定你在测试中使用的输入rand5()产生的是0-4，而不是这个解决方案中指定的1-5吗？ - Adam Rosenfield
5将均匀分布的数相加并不会得到一个均匀分布的数。事实上，你只需要将6个这样的均匀分布变量相加，就可以得到一个合理的正态分布近似值。 - Mitch Wheat
2@MitchWheat - 实际上，将两个均匀分布的整数相加确实会得到一个均匀分布的随机整数，前提是每个可能的总和都可以以恰好一种方式生成。在表达式
5 * rand5() + rand5() 中恰好符合这种情况。 - Ted Hopp30
算法：
数字7可以用3位二进制数表示。
使用rand(5)随机填充每个二进制位，填充0或1。
例如：调用rand(5)并且
如果结果是1或2，则填充0
如果结果是4或5，则填充1
如果结果是3，则忽略并重新进行（拒绝采样）
通过这种方式，我们可以随机填充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;
}
}
}
- Anand
6
1总有一个微弱的停机问题幽灵存在，因为一个糟糕的随机数生成器可能会在某个时候生成大量的三。 - Alex North-Keys
如果结果为1或2，则用0填充位；如果结果为4或5，则用1填充位。为什么接受1、2、4、5，而拒绝3？你能解释一下吗？ - gkns
@gkns，这里没有逻辑，你可以让1和2表示填充0位，3和4表示填充1位。重要的是每个选项出现的概率都是50％，从而确保您的函数的随机性至少与原始rand（5）函数一样随机。这是一个很好的解决方案！ - Mo Beigi
这既不简单也不高效。每个 random_7 调用 random_5 的次数最多为 3 次，通常更多。本页面上的其他解决方案更接近实际最佳解决方案，大约为 2.2。 - Eyal
这不会给你一个在0到7之间的随机数，而不是1到7吗？ - NicholasFolk
1没事了，我错过了“while returnValue == 0”的部分。 - NicholasFolk
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 );
}
}
- Mike F
1
2一个正确的解决方案，每次调用rand7()平均调用rand5() 30/7 = 4.29次。 - Adam Rosenfield
18
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
编辑：那并不完全正确。假设 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]是在给定n次调用rand5的情况下，output=x可能发生的次数。
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]
- BCS
6
9这不是一个均匀分布。它非常接近均匀分布，但并非完全均匀。 - Adam Rosenfield
啊！骰子和7。如果你要说我错了，你不应该把证明留给读者作为练习。 - BCS
46证明这不是均匀的很简单：随机性有5^7种可能，而因为5^7不是7的倍数，所以7个和相等的概率不可能相同。（基本上，这可以归结为7与5互质，或者换句话说，在5进制下，1/7不是一个有限小数。）实际上，即使在这种约束条件下，这也不是“最均匀”的可能情况。直接计算表明，在5^7=78125个和中，得到值1至7的次数为{1:11145, 2:11120, 3:11120, 4:11145, 5:11190, 6:11215, 7:11190}。 - ShreevatsaR
@ShreevatsaR 那么，如果我们不是对 rand5() 的结果进行七次求和，而是进行 5*7 次取值，那行吗？35^7 % 7 = 35^5 % 7 = 0。 - kba
5无论你调用 rand5() 多少次，你都不会得到均匀分布。如果你调用 N 次，会有 5^N 种可能的输出结果，而这个数不能被7整除。（例如，如果你调用35次，则有5^35种可能的结果，而不是35^7。）随着调用次数的增加（可以是任何数字，不必是7的倍数），你将越来越接近于均匀分布，但我认为，与其使用大量的rand()调用，还不如使用前面的答案中提供的概率算法，该算法生成完全均匀的分布，并且对rand()的期望调用次数很小。 - ShreevatsaR
@engin 这将使其既不均匀也不在正确的范围内。 - BCS
16
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
- Nescio
2
2一个正确的解决方案，使每次调用rand7()平均调用rand5() 30/7 = 4.29次。 - Adam Rosenfield
4算法需要进行左移操作才能正常工作：
ans += (r < 3) << i。 - woolfie13
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 的数字，然后取模 7，我们就可以得到一个接近均匀的 rand7 生成器。0 到 15,624 的数字可以通过掷 6 次 rand5 并使用它们来形成一个基数为 5 的数字的位数来均匀生成：
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
然而，模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
理论
15624这个数字并非随机选择，而是可以通过费马小定理来发现。该定理指出，如果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)
- Thirlan
1
2这个生成器是准确的，但并非完全均匀。要看到这一点，请考虑在[0,15624]范围内的均匀生成器有15625种可能的结果，这不可被7整除。这会对数字0产生偏差（它有2233/15625的机会，而其他数字只有2232/15625）。尽管使用费马小定理可能乍一看似乎正确，但它说的是(5^6)%7=1，而不是(5^6)%7=0。后者显然对于任何指数都是不可能的，因为5和7都是质数。我认为这仍然是一个可接受的解决方案，并且我已经编辑了您的帖子以反映这一点。 - aviator
13
以下代码通过使用生成1到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;
}
- Jason
4
2一个正确的解决方案（让你领先于曲线），虽然不是非常高效。这使得每个公平硬币翻转平均需要 25/6 = 4.17 次调用 random_5_mod_2，对于每次调用 random_7() 的总平均调用次数为 100/7 = 14.3 次 random_5()。 - Adam Rosenfield
与其他解决方案相比，此解决方案的优点在于它可以轻松扩展，以生成任何其他均匀分布范围。只需随机选择每个位，重新滚动无效值（例如我们当前解决方案中产生8个数字的值0）。 - DenTheMan
1可能的无限循环等。 - robermorales
1@robermorales：极不可能。 - jason
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
7 * rand5() / 5怎么样？ - kiwixz