给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
上面引用了一些优雅的算法,但这里有一种方法可以接近它,尽管它可能是迂回的。我假设的值是从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,我们只需再次运行R7,如果它返回7:
int R7() {
do {
x = R8();
} while (x > 6)
return x;
}
迂回的解决方案是从R5生成R2(就像我们从R8生成R7一样),然后从R2生成R8,然后从R8生成R7。
其他回答
这里似乎没有提到的另一个答案:
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之间的随机值。它被追加(以7为基数)到一个0到4(包括4)之间的随机值,结果除以5,得到一个0到6(包括6)范围内的新随机值。R开始时有很大的偏差(R = 3是非常有偏差的!),但每次迭代都将偏差除以5。
这种方法不是完全均匀的;然而,偏差是微乎其微的。数量级为1/(2**64)这种方法的重要之处在于它具有恒定的执行时间(假设rand5()也具有恒定的执行时间)。理论上不需要担心一个不走运的调用可能永远迭代地选择坏值。
此外,还有一个讽刺的回答(有意无意,它已经被覆盖了):
1-5已经在1-7的范围内,因此下面是一个有效的实现:
int rand7() {
return rand5();
}
问题没有要求均匀分布。
这里我们使用约定的rand(n) -> [0, n - 1]
从我读到的许多答案中,它们要么提供了一致性,要么提供了暂停保证,但不能同时提供(adam rosenfeld的第二个答案可能)。
然而,这样做是可能的。我们基本上有这样的分布:
这给[0-6]上的分布留下了一个漏洞:5和6没有 发生的概率。想象一下,现在我们试图通过移动 概率分布和求和。
事实上,我们可以把初始分布平移1,然后 重复将得到的分布与移位的初始分布相加 2,然后3,以此类推,直到7,不包括在内(我们涵盖了整个范围)。 如下图所示。颜色的顺序,对应 步骤,是蓝色->绿色->青色->白色->品红->黄色->红色。
因为每个插槽由7个移位分布中的5个覆盖(移位从 0到6),因为我们假设随机数是独立于1的 Ran5()呼叫另一个,我们获得
p(x) = 5 / 35 = 1 / 7 for all x in [0, 6]
这意味着,给定来自ran5()的7个独立随机数,我们可以 计算一个在[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
这很好,尽管远非完美。事实上,我们的一个假设是 在这个实现中很可能是false:我们使用一个PRNG,因此,结果 的值依赖于上一个结果。
也就是说,使用一个真正随机的数字来源,输出也应该是 真正随机的。这个算法在任何情况下都终止。
但这是有代价的:我们需要为一个rand7()调用7次rand5() 调用。
这相当于Adam Rosenfield的解决方案,但对一些读者来说可能更清楚一些。它假设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;
}
How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.
就像亚当说的,在最坏的情况下,它可以一直运行下去,但从统计上看,最坏的情况永远不会发生。:)
下面使用随机数发生器在{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;
}
简单高效:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(灵感来自你最喜欢的“程序员”卡通?)