给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
Here's a solution that fits entirely within integers and is within about 4% of optimal (i.e. uses 1.26 random numbers in {0..4} for every one in {0..6}). The code's in Scala, but the math should be reasonably clear in any language: you take advantage of the fact that 7^9 + 7^8 is very close to 5^11. So you pick an 11 digit number in base 5, and then interpret it as a 9 digit number in base 7 if it's in range (giving 9 base 7 numbers), or as an 8 digit number if it's over the 9 digit number, etc.:
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范围内,就像预期的近似高斯分布一样)。
其他回答
你需要的函数是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
下面使用随机数发生器在{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;
}
这里我们使用约定的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() 调用。
面对这么复杂的答案,我觉得自己很蠢。
为什么不能:
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?
对于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