给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。


当前回答

除了我的第一个答案,我想再补充一个答案。这个答案试图最小化每次调用rand7()时对rand5()的调用次数,以最大限度地利用随机性。也就是说,如果你认为随机性是一种宝贵的资源,我们就会尽可能多地利用它,而不丢弃任何随机比特。这个答案也与伊万的回答中的逻辑有一些相似之处。

The entropy of a random variable is a well-defined quantity. For a random variable which takes on N states with equal probabilities (a uniform distribution), the entropy is log2 N. Thus, rand5() has approximately 2.32193 bits of entropy, and rand7() has about 2.80735 bits of entropy. If we hope to maximize our use of randomness, we need to use all 2.32193 bits of entropy from each call to rand5(), and apply them to generating 2.80735 bits of entropy needed for each call to rand7(). The fundamental limit, then, is that we can do no better than log(7)/log(5) = 1.20906 calls to rand5() per call to rand7().

附注:除非另有说明,否则此答案中的所有对数都将以2为底。Rand5()将被假定为返回范围[0,4]的数字,rand7()将被假定为返回范围[0,6]的数字。分别将范围调整为[1,5]和[1,7]是很简单的。

So how do we do it? We generate an infinitely precise random real number between 0 and 1 (pretend for the moment that we could actually compute and store such an infinitely precise number -- we'll fix this later). We can generate such a number by generating its digits in base 5: we pick the random number 0.a1a2a3..., where each digit ai is chosen by a call to rand5(). For example, if our RNG chose ai = 1 for all i, then ignoring the fact that that isn't very random, that would correspond to the real number 1/5 + 1/52 + 1/53 + ... = 1/4 (sum of a geometric series).

Ok, so we've picked a random real number between 0 and 1. I now claim that such a random number is uniformly distributed. Intuitively, this is easy to understand, since each digit was picked uniformly, and the number is infinitely precise. However, a formal proof of this is somewhat more involved, since now we're dealing with a continuous distribution instead of a discrete distribution, so we need to prove that the probability that our number lies in an interval [a, b] equals the length of that interval, b - a. The proof is left as an exercise for the reader =).

现在我们有一个从范围[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 结果的积分部分是下一个以7为基数的数字 减去积分部分,只留下小数部分 转到第一步

为了处理无限精度的问题,我们计算一个部分结果,并存储结果的上界。也就是说,假设我们调用rand5()两次,两次都返回1。到目前为止,我们生成的数字是0.11(以5为基数)。无论rand5()调用的无限序列的剩余部分产生什么,我们生成的随机实数永远不会大于0.12:0.11≤0.11xyz…< 0.12。

因此,跟踪当前数字到目前为止,以及它可能的最大值,我们将两个数字都转换为以7为底。如果它们对前k位一致,那么我们就可以安全地输出下k位——不管以5为底的无限流是什么,它们永远不会影响以7为底表示的下k位!

这就是生成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的幂增长很快。因此,在生成大量随机数后,由于大算术,性能将开始明显下降。但请记住,我的目标是最大化随机位的使用,而不是最大化性能(尽管这是次要目标)。

在一次运行中,我对rand5()进行了12091次调用,对rand7()进行了10000次调用,实现了log(7)/log(5)次调用的最小值,平均为4位有效数字,结果输出是均匀的。

为了将这段代码移植到一种没有内置任意大整数的语言中,您必须将pow5和pow7的值限制为本地整型类型的最大值——如果它们变得太大,则重置所有内容并重新开始。这将使每次调用rand7()时对rand5()的平均调用次数略有增加,但希望即使对于32或64位整数也不会增加太多。

其他回答

这个问题的主要概念是关于正态分布的,这里提供了一个简单的递归解决这个问题的方法

假设我们已经在我们的作用域中有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 复合ans by rand5() + twoway * 5,这正是rand10()的结果,如果这不符合我们的需要(1~7),然后我们再次运行rand7。

附注:我们不能在第二部分直接运行while循环,因为双向的每个概率都需要是单独的。

但是有一个权衡,因为第一部分中的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的值的概率,但这可能是这个问题的最短答案。

这个怎么样

rand5 () % + rand5 (2) + 2 (2) % + rand5 rand5 () (2) % + rand5 % + rand5 (2) 2

不确定这是均匀分布的。有什么建议吗?

从一个扩大浮动范围的链接来到这里。这个更有趣。而不是我是如何得出结论的,我突然想到,对于一个给定的随机整数生成函数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,我称之为精度是你想要的浮点生成器的良好粒度的程度。可以把这看作是对rand7的每次调用对rand5的调用数。

但我意识到,如果你把b设为底数+1(在这种情况下是4+1 = 5),这是一个最佳点,你会得到均匀的分布。首先摆脱这个1-5生成器,它实际上是rand4() + 1:

function rand4(){
    return Math.random() * 5 | 0;
}

为了达到这个目的,你可以用rand5()-1替换rand4

接下来是将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 include)转换为任何其他浮动范围,然后将其降级为整数。这里我们的底是4,因为我们处理的是rand4,因此b=5的值会给你一个均匀分布。当b增长超过4时,你将开始在分布中引入周期性间隙。我测试了从2到8的b值,每个值都有3000分,并与原生数学进行了比较。随机的javascript,在我看来甚至比本机本身更好:

http://jsfiddle.net/ibowankenobi/r57v432t/

对于上面的链接,单击分布顶部的“bin”按钮以减小分箱大小。最后一个图表是原生数学。随机的,第四个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

为什么不除以5再乘以7,然后四舍五入呢?(当然,你必须使用浮点数no.)

它比其他解决方案更简单、更可靠(真的吗?)例如,在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

这不是很容易吗?

这里似乎没有提到的另一个答案:

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();
}

问题没有要求均匀分布。