给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
我想到了一个解决这个问题的有趣方法,想和大家分享一下。
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:)
其他回答
这是我在看过别人的答案后得出的最简单的答案:
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()结果的所有可能组合。我使用与解决方案代码中相同的筛选器进行测试。你可以看到所有的结果都是相等的,因为它们有相同的值。
给定一个生成1到5rand5()范围内随机整数的函数,编写一个生成1到7rand7()范围内随机整数的函数
在我建议的解决方案中,我只调用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
Python:有一个简单的两行答案,它使用空间代数和模量的组合。这不是直观的。我对它的解释令人困惑,但却是正确的。
知道5*7=35 7/5 = 1余数为2。如何保证余数之和始终为0?5*[7/5 = 1余数2]——> 35/5 = 7余数0
想象一下,我们有一条丝带,缠在一根周长为7的杆子上。丝带需要35个单位才能均匀地缠绕。随机选择7个色带片段len=[1…5]。忽略换行的有效长度与将rand5()转换为rand7()的方法相同。
import numpy as np
import pandas as pd
# display is a notebook function FYI
def rand5(): ## random uniform int [1...5]
return np.random.randint(1,6)
n_trials = 1000
samples = [rand5() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=True))
# 4 0.2042
# 5 0.2041
# 2 0.2010
# 1 0.1981
# 3 0.1926
# dtype: float64
def rand7(): # magic algebra
x = sum(rand5() for _ in range(7))
return x%7 + 1
samples = [rand7() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=False))
# 6 1475
# 2 1475
# 3 1456
# 1 1423
# 7 1419
# 4 1393
# 5 1359
# dtype: int64
df = pd.DataFrame([
pd.Series([rand7() for _ in range(n_trials)]).value_counts(normalize=True)
for _ in range(1000)
])
df.describe()
# 1 2 3 4 5 6 7
# count 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000
# mean 0.142885 0.142928 0.142523 0.142266 0.142704 0.143048 0.143646
# std 0.010807 0.011526 0.010966 0.011223 0.011052 0.010983 0.011153
# min 0.112000 0.108000 0.101000 0.110000 0.100000 0.109000 0.110000
# 25% 0.135000 0.135000 0.135000 0.135000 0.135000 0.135000 0.136000
# 50% 0.143000 0.142000 0.143000 0.142000 0.143000 0.142000 0.143000
# 75% 0.151000 0.151000 0.150000 0.150000 0.150000 0.150000 0.151000
# max 0.174000 0.181000 0.175000 0.178000 0.189000 0.176000 0.179000
为什么不除以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 value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
与选定的解决方案不同,该算法将在常数时间内运行。然而,它对rand5的调用比所选解决方案的平均运行时间多2次。
请注意,这个生成器并不完美(数字0比任何其他数字都有0.0064%的可能性),但对于大多数实际目的,保证恒定的时间可能比这种不准确性更重要。
解释
这个解源于数字15624能被7整除的事实,因此,如果我们可以随机且均匀地生成从0到15624的数字,然后对7取余,我们就可以得到一个近乎均匀的rand7生成器。将rand5滚动6次,将0到15624之间的数字统一生成,并使用这些数字组成以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
So
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)