pra*_*een 683 random puzzle algorithm
给定产生1到5范围内的随机整数的函数,写一个产生1到7范围内随机整数的函数.
Rob*_*fee 561
这相当于亚当罗森菲尔德的解决方案,但对于一些读者可能会更清楚一些.它假设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;
}
它是如何工作的？想象一下:想象一下在纸上打印出这个双维阵列,将它固定在飞镖板上并随意投掷飞镖.如果您达到非零值,则它是1到7之间的统计随机值,因为有相同数量的非零值可供选择.如果你达到零,只要继续投掷飞镖直到你达到非零.这就是这段代码的作用:i和j索引在飞镖板上随机选择一个位置,如果我们没有得到好的结果,我们就会继续投掷飞镖.
就像亚当说的那样,在最坏的情况下,这可以永远运行,但从统计上来说,最糟糕的情况从未发生.:)
Ada*_*eld 347
没有(完全正确的)解决方案将在恒定的时间内运行,因为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循环迭代的运行时间,但是永远循环的概率极小.
Ada*_*eld 153
除了我的第一个答案,我想补充一个答案.此答案尝试最小化rand5()每次呼叫的呼叫次数rand7(),以最大化随机性的使用.也就是说,如果你认为随机性是一种宝贵的资源,我们希望尽可能多地使用随机性,而不丢弃任何随机位.这个答案也与伊万答案中提出的逻辑有一些相似之处.
随机变量的熵是明确定义的数量.对于具有相等概率(均匀分布)的N个状态的随机变量,熵是log 2 N.因此,rand5()具有大约2.32193比特的熵,并且rand7()具有大约2.80735比特的熵.如果我们希望最大化我们对随机性的使用,我们需要在每次调用时使用所有2.32193位的熵rand5(),并将它们应用于生成每次调用所需的2.80735位熵rand7().那么,基本限制是我们不能比rand5()每次调用的log(7)/ log(5)= 1.20906调用更好rand7().
附注:除非另有说明,否则本答案中的所有对数均为基数2. rand5()将假设返回[0,4]范围内的数字,并rand7()假设返回[0,6]范围内的数字.将范围分别调整为[1,5]和[1,7]是微不足道的.
那我们该怎么做呢？我们生成一个介于0和1之间的无限精确的随机实数(假装我们实际上可以计算并存储这样一个无限精确的数字 - 我们稍后会修复它).我们可以通过在基数5中生成其数字来生成这样的数字:我们选择随机数0 a1 a2 a3 ...,其中每个数字a i通过调用来选择rand5().例如,如果我们的RNG i为所有人选择a = 1 i,那么忽略不是非常随机的事实,这将对应于实数1/5 + 1/5 2 + 1/5 3 + ... = 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的一种方法如下:
为了处理无限精度的问题,我们计算了部分结果,并且我们还存储了结果可能的上限.也就是说,假设我们已经调用了rand5()两次并且它两次都返回了1次.到目前为止我们生成的数字是0.11(基数5).无论生成的无限系列调用的其余部分是什么rand5(),我们生成的随机实数将永远不会大于0.12:始终为0.11≤0.11xyz... <0.12.
因此,跟踪到目前为止的当前数字,以及它可能采取的最大值,我们将这两个数字转换为基数7.如果他们同意第一个k数字,那么我们可以安全地输出下一个k数字 - 无论是什么基数为5位的无限流,它们永远不会影响k基数7表示的下一个数字!
这就是算法 - 为了生成下一个输出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的力量迅速增长.因此,由于bignum算法,在生成大量随机数后,性能将开始明显降低.但请记住,我的目标是最大化随机位的使用,而不是最大化性能(尽管这是次要目标).
在一次运行中,我进行了12091次调用以rand5()进行10000次调用rand7(),平均达到log(7)/ log(5)调用的最小值为4个有效数字,并且得到的输出是均匀的.
为了将此代码移植到一个没有内置任意大整数的语言,你必须限制你的原生整数类型的值pow5和pow7最大值 - 如果它们变得太大,那么重置一切都重新开始.这会将rand5()每次调用的平均调用次数rand7()略微增加,但希望即使对于32位或64位整数也不应增加太多.
Eya*_*yal 36
(我偷了亚当罗森菲尔德的答案,让它跑得快了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);
}
我们跟踪循环在变量中可以产生的最大值max.如果到目前为止reult在max%7和max-1之间,则结果将在该范围内均匀分布.如果没有,我们使用余数,它在0和最大%7-1之间是随机的,另一次调用rand()来产生一个新的数字和一个新的最大值.然后我们重新开始.
编辑:期望调用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()
小智 28
算法:
图7的序列可以以3比特的顺序表示
使用rand(5)随机填充每个位0或1.
例如:调用rand(5)和
如果结果为1或2,
如果结果为4或5则将该位填充为0 ,
如果结果为3则将该位填充为1 ,然后忽略并再次执行(拒绝)
这样我们可以用0/1随机填充3位,从而得到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;
}
}
}
小智 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 );
}
}
BCS*_*BCS 16
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1
编辑:这不太奏效.它在1000左右大约2个部分(假设完美的兰德5).水桶得到:
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]是多少的方式output=x可能会发生给n来电rand5.
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]
Nes*_*cio 15
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
jas*_*son 13
以下使用随机数发生器在{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;
}
小智 12
如果我们考虑尝试给出最有效答案的附加约束,即给出输入流的附加约束,来自1-5 I的长度均匀分布的整数m输出一个流O,从最长的相对长度的1-7开始均匀分布的整数对m,说L(m).
分析这个的最简单方法是分别处理流I和O5-ary和7-ary数.这是通过主要答案的获取流的概念a1, a2, a3,... -> a1+5*a2+5^2*a3+..和类似的流来实现的O.
然后,如果我们采用长度的输入流的一部分m choose n s.t. 5^m-7^n=c,c>0尽可能小.再有就是从长度为m为整数输入流的均匀映射从1到5^m和从整数从1到另一个均匀地图7^n长度的输出流n,其中我们可能必须从输入流失去一些情况下当所述映射整数超过7^n.
因此,这给出了一个值L(m)围绕m (log5/log7)这大约是.82m.
与上述分析的难度是方程5^m-7^n=c这是不容易精确地解决和的情况下从所述统一值1到5^m超过7^n和我们输效率.
问题是如何接近m(log5/log7)的最佳可能值.例如,当这个数接近整数时,我们能找到一种方法来实现这个精确的整数输出值吗？
如果5^m-7^n=c那么从输入流我们有效地生成一个统一的随机数0,(5^m)-1并且不使用任何高于的值7^n.但是,可以挽救这些值并再次使用.它们有效地生成从1到1的统一数字序列5^m-7^n.因此,我们可以尝试使用它们并将它们转换为7位数,以便我们可以创建更多的输出值.
如果我们让它T7(X)成为random(1-7)从均匀的大小输入派生的整数输出序列的平均长度X,并假设5^m=7^n0+7^n1+7^n2+...+7^nr+s, s<7.
然后,T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)因为我们有一个长度没有序列,概率为7 ^ n0/5 ^ m,残差长度5^m-7^n0为概率(5^m-7^n0)/5^m).
如果我们继续代替我们获得:
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
于是
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
另一种方法是:
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
最好的情况是我原来的一个在哪里5^m=7^n+s,哪里s<7.
然后T7(5^m) = nx(7^n)/(7^n+s) = n+o(1) = m (Log5/Log7)+o(1)和以前一样.
最糟糕的情况是我们只能找到k和st 5 ^ m = kx7 + s.
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
其他案件介于两者之间.看看我们能为非常大的m做得多好,这将是有趣的,即我们得到错误项有多好:
T7(5^m) = m (Log5/Log7)+e(m)
e(m) = o(1)一般来说似乎不可能实现,但希望我们可以证明e(m)=o(m).
然后整个事情依赖于7个数字的分布5^m为各种值m.
我确信有很多理论可以解决这个问题,我可能会在某些方面回顾一下.
Wil*_*ung 11
这里有家庭作业问题吗？
此函数执行原始"基数5"数学运算以生成0到6之间的数字.
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
Jam*_*hon 10
这是Adam的答案的有效Python实现.
import random
def rand5():
return random.randint(1, 5)
def rand7():
while True:
r = 5 * (rand5() - 1) + rand5()
#r is now uniformly random between 1 and 25
if (r <= 21):
break
#result is now uniformly random between 1 and 7
return r % 7 + 1
我喜欢抛出我正在研究Python的算法,所以我可以玩它们,我想我会在这里发布它,希望它对那里的人有用,而不是花了很长时间才能拼凑起来.
小智 10
为什么不这么简单？
int random7() {
return random5() + (random5() % 3);
}
由于模数的原因,在此解决方案中获得1和7的可能性较低,但是,如果您只是想要一个快速且可读的解决方案,那么这就是要走的路.
Thi*_*lan 10
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之间的数字,然后取mod 7,我们就可以获得一个接近均匀的rand7生成器.0到15,624之间的数字可以通过滚动rand5 6次并使用它们形成基数为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
所以
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
理论
数字15,624不是随机选择的,但可以使用fermat的小定理来发现,该定理指出如果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的小偏差.
假设rand(n) 在这里意味着"从0到n-1的均匀分布中的随机整数",这里是使用Python的randint的代码示例,它具有这种效果.它仅使用randint(5)和常量来产生randint(7)的效果.实际上有点傻
from random import randint
sum = 7
while sum >= 7:
first = randint(0,5)
toadd = 9999
while toadd>1:
toadd = randint(0,5)
if toadd:
sum = first+5
else:
sum = first
assert 7>sum>=0
print sum
亚当罗森菲尔德正确答案背后的前提是:
当n等于2时,你有4个扔掉的可能性:y = {22,23,24,25}.如果你使用n等于6,你只有1次丢弃:y = {15625}.
5 ^ 6
= 15625 7*2232 = 15624
你多次调用rand5.但是,获得丢弃值(或无限循环)的可能性要小得多.如果有办法让y没有可能的丢弃值,我还没有找到它.
这是我的答案:
static struct rand_buffer {
unsigned v, count;
} buf2, buf3;
void push (struct rand_buffer *buf, unsigned n, unsigned v)
{
buf->v = buf->v * n + v;
++buf->count;
}
#define PUSH(n, v) push (&buf##n, n, v)
int rand16 (void)
{
int v = buf2.v & 0xf;
buf2.v >>= 4;
buf2.count -= 4;
return v;
}
int rand9 (void)
{
int v = buf3.v % 9;
buf3.v /= 9;
buf3.count -= 2;
return v;
}
int rand7 (void)
{
if (buf3.count >= 2) {
int v = rand9 ();
if (v < 7)
return v % 7 + 1;
PUSH (2, v - 7);
}
for (;;) {
if (buf2.count >= 4) {
int v = rand16 ();
if (v < 14) {
PUSH (2, v / 7);
return v % 7 + 1;
}
PUSH (2, v - 14);
}
// Get a number between 0 & 25
int v = 5 * (rand5 () - 1) + rand5 () - 1;
if (v < 21) {
PUSH (3, v / 7);
return v % 7 + 1;
}
v -= 21;
PUSH (2, v & 1);
PUSH (2, v >> 1);
}
}
它比其他人复杂一点,但我相信它最大限度地减少了对rand5的调用.与其他解决方案一样,它可能会循环很长时间.
简单高效:
int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}
(灵感来自你最喜欢的"程序员"漫画？).
小智 6
只要没有可供选择的七种可能性,绘制另一个随机数,将可能性的数量乘以5.在Perl中:
$num = 0;
$possibilities = 1;
sub rand7
{
while( $possibilities < 7 )
{
$num = $num * 5 + int(rand(5));
$possibilities *= 5;
}
my $result = $num % 7;
$num = int( $num / 7 );
$possibilities /= 7;
return $result;
}
我不喜欢从1开始的范围,所以我将从0开始:-)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}
你去,统一发布和零rand5电话.
def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed
需要事先设定种子.
我知道它已被回答,但这似乎工作正常,但我不能告诉你它是否有偏见.我的"测试"表明它至少是合理的.
也许亚当罗森菲尔德会好心评论？
我(天真？)的想法是这样的:
累积rand5,直到有足够的随机位来制作rand7.这最多需要2兰特5.为了得到rand7号码,我使用了积累值mod 7.
为了避免累加器溢出,并且由于累加器是mod 7,那么我采用累加器的mod 7:
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
rand7()函数如下:
(我让rand5的范围是0-4,rand7同样是0-6.)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
编辑:为1亿次试验添加了结果.
'真实'rand函数mod 5或7
rand5:avg = 1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 rand7:avg = 3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046
我的rand7
平均看起来不错,数字分布看起来也不错.
randt:avg = 3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943