将随机范围从1-5扩展到1-7

给定一个产生1到5范围内随机整数的函数，编写一个产生1到7范围内随机整数的函数。

220399 次浏览
小开

这里允许有家庭作业问题吗？

此函数执行粗略的“基数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;
}
小开

没有（完全正确的）解决方案可以在恒定的时间内运行，因为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次循环迭代的预期运行时间，但永远循环的可能性微乎其微。

小开 
int ans = 0;
while (ans == 0)
{
for (int i=0; i<3; i++)
{
while ((r = rand5()) == 3){};
ans += (r < 3) >> i
}
}
小开 
rand7() = (rand5()+rand5()+rand5()+rand5()+rand5()+rand5()+rand5())%7+1

编辑：这并不完全有效。它在1000中偏离了大约2个部分（假设一个完美的rand5）。桶得到：

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]是给定n调用rand5时output=x可能发生的次数。

  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]
小开 
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 );
}
}
小开

php中的解决方案

<?php
function random_5(){
return rand(1,5);
}




function random_7(){
$total = 0;


for($i=0;$i<7;$i++){
$total += random_5();
}


return ($total%7)+1;
}


echo random_7();
?>
小开

下面使用随机数生成器在{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;
}
小开

假设这里的兰特（n）意味着“从到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
小开

（我偷了Adam Rosenfeld的回答并使其运行速度提高了约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和max%7-1之间随机，并再次调用rand（）来创建一个新数字和新的max。然后我们重新开始。

编辑：期望调用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()
小开

产生近似均匀分布的恒定时间解。诀窍是625恰好可以被7整除，当你建立到这个范围时，你可以得到均匀的分布。

编辑：我的错，我算错了，但我不会拉它，我会离开它，以防有人发现它有用/有趣。它确实实际上毕竟有效…：）

int rand5()
{
return (rand() % 5) + 1;
}


int rand25()
{
return (5 * (rand5() - 1) + rand5());
}


int rand625()
{
return (25 * (rand25() - 1) + rand25());
}


int rand7()
{
return ((625 * (rand625() - 1) + rand625()) - 1) % 7 + 1;
}
小开 
int rand7()
{
int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
return rand5() + zero_one_or_two ;
}
小开

在所有这些复杂的答案面前我感到愚蠢。

为什么不能是：

int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}

?

小开 
#!/usr/bin/env ruby
class Integer
def rand7
rand(6)+1
end
end


def rand5
rand(4)+1
end


x = rand5() # x => int between 1 and 5


y = x.rand7() # y => int between 1 and 7

…尽管这可能被认为是作弊…

小开

我已经玩过了，我为这个Rand（7）算法编写了“测试环境”。例如，如果你想尝试什么分布给出你的算法，或者生成所有不同的随机值需要多少迭代（对于Rand（7）1-7），你可以使用它。

我的核心算法是这样的：

return (Rand5() + Rand5()) % 7 + 1;

井的均匀分布不亚于亚当·罗森菲尔德的。（我把它包含在我的代码片段里了）

private static int Rand7WithRand5()
{
//PUT YOU FAVOURITE ALGORITHM HERE//


//1. Stackoverflow winner
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;


//My 2 cents
//return (Rand5() + Rand5()) % 7 + 1;
}

这个“测试环境”可以采用任何Rand（n）算法并对其进行测试和评估（分布和速度）。只需将您的代码放入“Rand7With Rand5”方法并运行代码片段。

一些观察：

  • Adam Rosenfield的算法没有比我更好的分布，无论如何，两种算法的分布都很糟糕。
  • 原生Rand7（random.Next(1, 8)）完成，因为它在大约200多次迭代中生成了给定间隔内的所有成员，Rand7With Rand5算法10k（大约30-70k）
  • 真正的挑战不是编写一个从Rand（5）生成Rand（7）的方法，而是生成或多或少均匀分布的值。
小开

这是亚当的回答的工作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，这样我就可以和它们一起玩了，我想我会把它贴在这里，希望它对外面的人有用，而不是花了很长时间才组合在一起。

小开

通过使用滚动总额，您可以同时

  • 保持平均分配；和
  • 不必牺牲随机序列中的任何元素。

这两个问题都是简单的rand(5)+rand(5)...类型解决方案的问题。以下Python代码显示了如何实现它（其中大部分是证明分发）。

import random
x = []
for i in range (0,7):
x.append (0)
t = 0
tt = 0
for i in range (0,700000):
########################################
#####            qq.py             #####
r = int (random.random () * 5)
t = (t + r) % 7
########################################
#####       qq_notsogood.py        #####
#r = 20
#while r > 6:
#r =     int (random.random () * 5)
#r = r + int (random.random () * 5)
#t = r
########################################
x[t] = x[t] + 1
tt = tt + 1
high = x[0]
low = x[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, x[i], 100.0 * x[i] / tt)
if x[i] < low:
low = x[i]
if x[i] > high:
high = x[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / tt)

这个输出显示了结果：

pax$ python qq.py
0:   99908 14.27257
1:  100029 14.28986
2:  100327 14.33243
3:  100395 14.34214
4:   99104 14.15771
5:   99829 14.26129
6:  100408 14.34400
Variation = 1304 (0.18629%)


pax$ python qq.py
0:   99547 14.22100
1:  100229 14.31843
2:  100078 14.29686
3:   99451 14.20729
4:  100284 14.32629
5:  100038 14.29114
6:  100373 14.33900
Variation = 922 (0.13171%)


pax$ python qq.py
0:  100481 14.35443
1:   99188 14.16971
2:  100284 14.32629
3:  100222 14.31743
4:   99960 14.28000
5:   99426 14.20371
6:  100439 14.34843
Variation = 1293 (0.18471%)

一个简单的rand(5)+rand(5)，忽略那些返回超过6的情况，典型的变化为18%，100次就是上面所示的方法：

pax$ python qq_notsogood.py
0:   31756 4.53657
1:   63304 9.04343
2:   95507 13.64386
3:  127825 18.26071
4:  158851 22.69300
5:  127567 18.22386
6:   95190 13.59857
Variation = 127095 (18.15643%)


pax$ python qq_notsogood.py
0:   31792 4.54171
1:   63637 9.09100
2:   95641 13.66300
3:  127627 18.23243
4:  158751 22.67871
5:  126782 18.11171
6:   95770 13.68143
Variation = 126959 (18.13700%)


pax$ python qq_notsogood.py
0:   31955 4.56500
1:   63485 9.06929
2:   94849 13.54986
3:  127737 18.24814
4:  159687 22.81243
5:  127391 18.19871
6:   94896 13.55657
Variation = 127732 (18.24743%)

而且，根据Nixuz的建议，我已经清理了脚本，因此您可以提取并使用rand7...内容：

import random


# rand5() returns 0 through 4 inclusive.


def rand5():
return int (random.random () * 5)


# rand7() generator returns 0 through 6 inclusive (using rand5()).


def rand7():
rand7ret = 0
while True:
rand7ret = (rand7ret + rand5()) % 7
yield rand7ret


# Number of test runs.


count = 700000


# Work out distribution.


distrib = [0,0,0,0,0,0,0]
rgen =rand7()
for i in range (0,count):
r = rgen.next()
distrib[r] = distrib[r] + 1


# Print distributions and calculate variation.


high = distrib[0]
low = distrib[0]
for i in range (0,7):
print "%d: %7d %.5f" % (i, distrib[i], 100.0 * distrib[i] / count)
if distrib[i] < low:
low = distrib[i]
if distrib[i] > high:
high = distrib[i]
diff = high - low
print "Variation = %d (%.5f%%)" % (diff, 100.0 * diff / count)
小开

这相当于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;
}

它是如何工作的？可以这样想：想象一下在纸上打印出这个二维数组，把它钉在一个飞镖板上，然后随机向它扔飞镖。如果你命中了一个非零值，它在统计上是一个介于1到7之间的随机值，因为有等量的非零值可供选择。如果你命中了零，就继续扔飞镖，直到你击中一个非零值。这就是这段代码所做的：i和j索引随机选择飞镖板上的一个位置，如果我们没有得到好的结果，我们就继续扔飞镖。

就像亚当说的，这可以在最坏的情况下永远运行，但统计上最坏的情况永远不会发生。：）

小开

如果我们考虑试图给出最有效答案的附加约束，即给定一个输入流I，其长度为1-5的均匀分布整数m输出一个流O，其长度为相对于m最长的1-7的均匀分布整数，例如L(m)。

最简单的分析方法是将流I和O分别视为5元和7元数。这是通过主要答案的想法来实现的，即取流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到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和s. t 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)。

然后，整个事情取决于m的各种值的5^m的7进制数字的分布。

我相信有很多理论可以涵盖这一点，我可能会在某个时候看一看并报告。

小开

这个答案更像是从Rand5函数中获得最大熵的实验。因此，t有点不清楚，几乎可以肯定比其他实现慢得多。

假设0-4的均匀分布和0-6的均匀分布：

public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}


private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}


private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;


public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}


public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}


ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;


private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}


private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}


public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}

每次调用Rand5添加到缓冲区的位数目前为4/5*2，因此为1.6。 如果包含1/5的概率值，则增加0.05，因此增加1.65，但请参阅代码中的注释，我不得不禁用它。

调用Rand7=3+1/8*（3+1/8*（3+1/8*（…
这是3+3/8+3/64+3/512…所以大约3.42

通过从7中提取信息，我每次调用回收1/8*1/7位，大约0.018

这给出了每个调用的净消耗3.4位，这意味着每个Rand7对Rand5的调用比率为2.125。最佳应该是2.1。

我想这种方法比这里的许多其他方法慢显着，除非调用Rand5的成本非常昂贵（比如调用一些外部熵源）。

小开

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

随机变量的熵是一个定义明确的量。对于一个随机变量，它呈现N个相等概率的状态（均匀分布），熵是log2 N。因此，rand5()大约有2.32193位的熵，rand7()大约有2.80735位的熵。如果我们希望最大限度地利用随机性，我们需要使用每次调用rand5()的所有2.32193位的熵，并将它们应用于生成每次调用rand7()所需的2.80735位的熵。那么，基本的限制是，每次调用rand7()，我们不能做得比log（7）/log（5）=1.20906次调用rand5()更好。

附注：除非另有说明，否则此答案中的所有对数都将以2为基数。rand5()将被假定为返回范围[0,4]内的数字，rand7()将被假定为返回范围[0,6]内的数字。将范围分别调整为[1,5]和[1,7]是微不足道的。

那么我们该怎么做呢？我们生成一个介于0和1之间的无限精确随机实数（假设我们实际上可以计算和存储这样一个无限精确的数字——我们稍后会解决这个问题）。我们可以通过在5进制中生成数字来生成这样一个数字：我们选择随机数0.a1a2aa0…，其中每个数字a1都是通过调用rand5()来选择的。例如，如果我们的RNG为所有i选择了a1=1，那么忽略这不是非常随机的事实，这将对应于实数1/5+1/5a3+1/5a4+…=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的一种方法如下：

  1. 乘以7
  2. 结果的整数部分是下一个以7为基数的数字
  3. 减去整数部分，只留下小数部分
  4. 转到步骤1

为了处理无限精度的问题，我们计算了一个部分结果，并且我们还存储了结果可能是什么的上限。也就是说，假设我们调用了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次调用，平均达到4个有效数字的log（7）/log（5）调用的最小值，结果是一致的。

为了将此代码移植到没有内置任意大整数的语言，您必须将pow5和pow7的值限制为本机整数类型的最大值-如果它们太大，则重置所有内容并重新开始。这将使每次调用的平均调用次数增加到rand5()到rand7()非常轻微，但希望即使对于32位或64位整数也不会增加太多。

小开

亚当·罗森菲尔德正确答案背后的前提是：

  • x=5^n（在他的情况下：n=2）
  • 操纵n rand5调用以获取范围[1， x]内的数字y
  • z=（（int）（x/7））*7
  • 如果y>z，再试一次。否则返回y%7+1

当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的调用。与其他解决方案一样，它很可能会循环很长时间。

小开

上面引用了一些优雅的算法，但是这里有一种方法来处理它，尽管它可能是迂回的。

R2=随机数生成器，给出小于2的值（样本空间={0,1}）
R8=随机数生成器给出小于8的值（样本空间={0,1,2,3,4,5,6,7}）

为了从R2生成R8，你将运行R2三次，并将所有3次运行的组合结果用作具有3位数字的二进制数。以下是R2运行三次时的值范围：

0 0-->0
.
.
1 1 1-->7

现在要从R8生成R7，如果它返回7，我们只需再次运行R7：

int R7() {
do {
x = R8();
} while (x > 6)
return x;
}

迂回的解决方案是从R5生成R2（就像我们从R8生成R7一样），然后从R2生成R8，然后从R8生成R7。

小开

为什么不简单点呢？

int random7() {
return random5() + (random5() % 3);
}

由于取模，在这个解决方案中获得1和7的机会较低，但是，如果你只是想要一个快速且可读的解决方案，这就是要走的路。

小开

只要没有七种可能性可供选择，就再画一个随机数，将可能性数乘以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;
}
小开

您需要的函数是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
小开

给你，统一分配和零rand5通话。

def rand7:
seed += 1
if seed >= 7:
seed = 0
yield seed

需要提前播种。

小开

这是一个完全适合整数并且在最佳值的4%内的解决方案（即在{0…4}中使用1.26个随机数来对应{0…6}中的每个随机数）。代码是用Scala编写的，但数学在任何语言中都应该相当清楚：你利用了7^9+7^8非常接近5^11的事实。所以你在基数5中选择一个11位数字，然后如果它在范围内（给出9个基数7），则将其解释为基数7中的9位数字，或者如果它超过9位数字，则将其解释为8位数字，等等：

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内，正如从近似高斯分布中预期的那样）。

小开

我知道它已经被回答了，但这似乎工作正常，但我不能告诉你它是否有偏见。我的测试表明它至少是合理的。

也许亚当·罗森菲尔德可以发表评论？

我的（天真？）想法是这样的：

累加rand5直到有足够的随机位来生成rand7。这最多需要2个rand5。为了获得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

小开

只需缩放第一个函数的输出

0) you have a number in range 1-5
1) subtract 1 to make it in range 0-4
2) multiply by (7-1)/(5-1) to make it in range 0-6
3) add 1 to increment the range: Now your result is in between 1-7
小开

简单高效：

int rand7 ( void )
{
return 4; // this number has been calculated using
// rand5() and is in the range 1..7
}

（灵感来自你最喜欢的“程序员”漫画是什么？）。

小开

我不喜欢从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;
}
小开 
function Rand7
put 200 into x
repeat while x > 118
put ((random(5)-1) * 25) + ((random(5)-1) * 5) + (random(5)-1) into x
end repeat
return (x mod 7) + 1
end Rand7

给Rand5打了三次电话，平均125次中只重复了6次。

将其视为一个5x5x5的3D数组，一遍又一遍地填充1到7和6个空格。在空格上重新滚动。rand5调用在该数组中创建一个三位数的五进制索引。

使用4D或更高的N维数组会有更少的重复，但这意味着对rand5函数的更多调用将成为标准。在更高的维度上，您将开始获得递减的效率回报。在我看来，三个似乎是一个很好的妥协，但我还没有相互测试以确定。这将是rand5特定的实现。

小开

算法介绍

7可以用3位的序列表示

使用rand（5）随机填充每个位0或1。
例如：调用rand（5）和

如果结果为1或2，则用0填充该位
如果结果是4或5，则用1填充位
如果结果是3，则忽略并重新执行（拒绝）

这样我们就可以用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;
}
}
}
小开 
int getOneToSeven(){
int added = 0;
for(int i = 1; i<=7; i++){
added += getOneToFive();
}
return (added)%7+1;
}
小开

这是我在查看其他人的答案后可以创建的最简单的答案：

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（）结果的所有可能组合。我使用与解决方案代码中相同的过滤器进行测试。您可以看到所有结果的可能性相同，因为它们具有相同的值。

小开 
extern int r5();


int r7() {
return ((r5() & 0x01) << 2 ) | ((r5() & 0x01) << 1 ) | (r5() & 0x01);
}
小开 
package CareerCup;


public class RangeTransform {
static int counter = (int)(Math.random() * 5 + 1);


private int func() {
return (int) (Math.random() * 5 + 1);
}


private int getMultiplier() {
return counter % 5 + 1;
}


public int rangeTransform() {
counter++;
int count = getMultiplier();
int mult = func() + 5 * count;
System.out.println("Mult is : " + 5 * count);
return (mult) % 7 + 1;
}


/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RangeTransform rangeTransform = new RangeTransform();
for (int i = 0; i < 35; i++)
System.out.println("Val is : " + rangeTransform.rangeTransform());
}
}
小开

为什么这行不通？除了给rand5（）打一个额外的电话？

i = rand5() + rand5() + (rand5() - 1) //Random number between 1 and 14


i = i % 7 + 1;
小开

这个怎么样

兰特5（）%2+兰特5（）%2+兰特5（）%2+兰特5（）%2+兰特5（）%2+兰特5（）%2+兰特5（）%2

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

小开

对于值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

小开 
rand25() =5*(rand5()-1) + rand5()


rand7() {
while(true) {
int r = rand25();
if (r < 21) return r%3;
}
}

为什么会这样：循环永远运行的概率是0。

小开

我想到了一个有趣的解决这个问题的方法，并想分享它。

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：）

小开

在php

function rand1to7() {
do {
$output_value = 0;
for ($i = 0; $i < 28; $i++) {
$output_value += rand1to5();
}
while ($output_value != 140);
$output_value -= 12;
return floor($output_value / 16);
}

循环以产生16到127之间的随机数，除以16以创建1到7.9375之间的浮点数，然后向下舍入以获得1到7之间的int。如果我没弄错，有16/112的机会得到7个结果中的任何一个。

小开

假设rand为所有位提供相等的权重，然后使用上限进行掩码。

int i = rand(5) ^ (rand(5) & 2);

rand(5)只能返回：1b、10b、11b、100b、101b。您只需要有时设置2位即可。

小开

以下是我发现的：

  1. 随机5产生1~5的范围，随机分布
  2. 如果我们运行3次并将它们加在一起，我们将得到3~15的范围，随机分布
  3. 在3~15范围内执行算术
    1. （3~15）-1=（2~14）
    2. （2~14）/2=（1~7）

然后我们得到一个1~7的范围，这就是我们要找的随机7。

小开

你为什么不除以5，乘以7，然后四舍五入呢？（当然，你必须使用浮点数no. s）

它比其他解决方案更容易和更可靠（真的吗？）。例如在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

不是那么容易吗？

小开

我首先想到的是这个。但我不知道它是否均匀分布。 在python中实现

导入随机

def rand5（）：

返回random.randint（1,5）

def rand7（）：

返回（（（rand5（）-1）*rand5（））%7）+1

小开 
int rand7()
{
return ( rand5() + (rand5()%3) );
}
  1. rand5（）-返回1-5之间的值
  2. rand5（）%3-返回0-2之间的值
  3. 所以，当总和的总价值将在1-7之间
小开

这是我的一般实现，给定范围[0， B-1]中的均匀生成器，生成范围[0， N-1]中的均匀。 

public class RandomUnif {


public static final int BASE_NUMBER = 5;


private static Random rand = new Random();


/** given generator, returns uniform integer in the range 0.. BASE_NUMBER-1
public static int randomBASE() {
return rand.nextInt(BASE_NUMBER);
}


/** returns uniform integer in the range 0..n-1 using randomBASE() */
public static int randomUnif(int n) {
int rand, factor;
if( n <= 1 ) return 0;
else if( n == BASE_NUMBER ) return randomBASE();
if( n < BASE_NUMBER ) {
factor = BASE_NUMBER / n;
do
rand = randomBASE() / factor;
while(rand >= n);
return rand;
} else {
factor = (n - 1) / BASE_NUMBER + 1;
do {
rand = factor * randomBASE() + randomUnif(factor);
} while(rand >= n);
return rand;
}
}
}

效率不高，但一般而紧凑。对基地发电机的平均调用：

 n  calls
2  1.250
3  1.644
4  1.252
5  1.000
6  3.763
7  3.185
8  2.821
9  2.495
10  2.250
11  3.646
12  3.316
13  3.060
14  2.853
15  2.650
16  2.814
17  2.644
18  2.502
19  2.361
20  2.248
21  2.382
22  2.277
23  2.175
24  2.082
25  2.000
26  5.472
27  5.280
28  5.119
29  4.899
小开

我们在这里使用公约rand(n) -> [0, n - 1]

从我读到的许多答案来看，它们要么提供一致性，要么提供停机保证，但不是两者兼而有之（亚当罗森菲尔德的第二个答案可能）。

然而，这是可能的。我们基本上有这样的分布：

rand5_proba.png

这在[0-6]的分布中给我们留下了一个漏洞：5和6没有 发生的概率。想象一下，现在我们试图通过移动 概率分布和求和。

实际上，我们可以将初始分布自身移动一，并且 通过求和得到的分布与初始分布移动 两个，然后三个等等，直到7，不包括在内（我们涵盖了整个范围）。 这如下图所示。颜色的顺序，对应于 步骤，是蓝色->绿色->青色->白色->品红色->黄色->红色。

fig_moving_average_proba.png

因为每个插槽被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，因此，结果 下一次调用的结果取决于上一次结果。

也就是说，使用真正随机的数字源，输出也应该是 真正的随机。这个算法在任何情况下都会终止。

但这是有代价的：我们需要7次调用rand5()才能获得一个rand7() 呼叫。

小开

这里有很多解决方案不能产生均匀分布，许多评论指出了这一点，但是问题没有说明作为要求。最简单的解决方案是：

int rand_7() { return rand_5(); }

1-5范围内的随机整数显然在1-7范围内。好吧，从技术上讲，最简单的解决方案是返回一个常数，但这太琐碎了。

然而，我认为rand_5函数的存在是一个转移注意力的问题。假设这个问题被问到“产生一个均匀分布的伪随机数生成器，其整数输出范围在1-7”。这是一个简单的问题（技术上不简单，但已经解决了，所以你可以查一下。）

另一方面，如果这个问题被解释为意味着你实际上有一个真正的随机数生成器，用于1-5范围内的整数（不是伪随机），那么解决方案是：

1) examine the rand_5 function
2) understand how it works
3) profit
小开

这个表达式足以得到1-7之间的随机整数

int j = ( rand5()*2 + 4 ) % 7 + 1;
小开 
function rand7() {
while (true) { //lowest base 5 random number > 7 reduces memory
int num = (rand5()-1)*5 + rand5()-1;
if (num < 21)  // improves performance
return 1 + num%7;
}
}

python代码：

from random import randint
def rand7():
while(True):
num = (randint(1, 5)-1)*5 + randint(1, 5)-1
if num < 21:
return 1 + num%7

100000次运行的测试分布：

>>> rnums = []
>>> for _ in range(100000):
rnums.append(rand7())
>>> {n:rnums.count(n) for n in set(rnums)}
{1: 15648, 2: 15741, 3: 15681, 4: 15847, 5: 15642, 6: 15806, 7: 15635}
小开

这与@RobMcAfee类似，只是我使用了魔术数字而不是2维数组。

int rand7() {
int m = 1203068;
int r = (m >> (rand5() - 1) * 5 + rand5() - 1) & 7;


return (r > 0) ? r : rand7();
}
小开

这个解决方案不会浪费任何熵，并给出范围内第一个可用的真正随机数。随着每次迭代，无法得到答案的概率被证明是降低的。在N次迭代中得到答案的概率是0到max（5^N）之间的随机数小于该范围内最大的7倍（max-max%7）的概率。必须迭代至少两次。但这必然适用于所有解决方案。

int random7() {
range = 1;
remainder = 0;


while (1) {
remainder = remainder * 5 + random5() - 1;
range = range * 5;


limit = range - (range % 7);
if (remainder < limit) return (remainder % 7) + 1;


remainder = remainder % 7;
range = range % 7;
}
}

数值上等同于：

r5=5;
num=random5()-1;
while (1) {
num=num*5+random5()-1;
r5=r5*5;
r7=r5-r5%7;
if (num<r7) return num%7+1;
}

第一个代码以模形式计算。第二个代码只是简单的数学。或者我在某个地方犯了错误。：-）

小开

这个解决方案的灵感来自Rob McAfee。
但是它不需要循环，结果是均匀分布：

// Returns 1-5
var rnd5 = function(){
return parseInt(Math.random() * 5, 10) + 1;
}
// Helper
var lastEdge = 0;
// Returns 1-7
var rnd7 = function () {
var map = [
[ 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 ]
];
var result = map[rnd5() - 1][rnd5() - 1];
if (result > 0) {
return result;
}
lastEdge++;
if (lastEdge > 7 ) {
lastEdge = 1;
}
return lastEdge;
};


// Test the a uniform distribution
results = {}; for(i=0; i < 700000;i++) { var rand = rnd7(); results[rand] = results[rand] ? results[rand] + 1 : 1;}
console.log(results)

结果：[1: 99560, 2: 99932, 3: 100355, 4: 100262, 5: 99603, 6: 100062, 7: 100226]

jsFiddle

小开

我想你们都想太多了。这个简单的解决办法行不通吗？

int rand7(void)
{
static int startpos = 0;
startpos = (startpos+5) % (5*7);
return (((startpos + rand5()-1)%7)+1);
}
小开

给定一个产生1到5范围内随机整数的函数rand5()，编写一个产生1到7范围内随机整数的函数rand7()

在我提出的解决方案中，我只调用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

小开

以下是利用C++11中的功能的答案

#include <functional>
#include <iostream>
#include <ostream>
#include <random>


int main()
{
std::random_device rd;
unsigned long seed = rd();
std::cout << "seed = " << seed << std::endl;


std::mt19937 engine(seed);


std::uniform_int_distribution<> dist(1, 5);
auto rand5 = std::bind(dist, engine);


const int n = 20;
for (int i = 0; i != n; ++i)
{
std::cout << rand5() << " ";
}
std::cout << std::endl;


// Use a lambda expression to define rand7
auto rand7 = [&rand5]()->int
{
for (int result = 0; ; result = 0)
{
// Take advantage of the fact that
// 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
// So we only have to discard one out of every 15625 numbers generated.


// Generate a 6-digit number in base 5
for (int i = 0; i != 6; ++i)
{
result = 5 * result + (rand5() - 1);
}


// result is in the range [0, 15625)
if (result == 15625 - 1)
{
// Discard this number
continue;
}


// We now know that result is in the range [0, 15624), a range that can
// be divided evenly into 7 buckets guaranteeing uniformity
result /= 2232;
return 1 + result;
}
};


for (int i = 0; i != n; ++i)
{
std::cout << rand7() << " ";
}
std::cout << std::endl;


return 0;
}
小开

简单的解决方案已经得到了很好的覆盖：为一个random7结果取两个random5样本，如果结果超出生成均匀分布的范围，则重新执行。如果您的目标是减少对random5的调用次数，这是非常浪费的-由于丢弃的样本数量，每个random7输出对random5的平均调用次数为2.38而不是2。

通过使用更多random5输入一次生成多个random7输出可以做得更好。对于使用31位整数计算的结果，最佳值是使用12个对random5的调用来生成9个random7输出，平均每个输出调用1.34次。这很有效，因为244140625个结果中只有2018983个需要废弃，或不到1%。

Python中的演示：

def random5():
return random.randint(1, 5)


def random7gen(n):
count = 0
while n > 0:
samples = 6 * 7**9
while samples >= 6 * 7**9:
samples = 0
for i in range(12):
samples = samples * 5 + random5() - 1
count += 1
samples //= 6
for outputs in range(9):
yield samples % 7 + 1, count
samples //= 7
count = 0
n -= 1
if n == 0: break


>>> from collections import Counter
>>> Counter(x for x,i in random7gen(10000000))
Counter({2: 1430293, 4: 1429298, 1: 1428832, 7: 1428571, 3: 1428204, 5: 1428134, 6: 1426668})
>>> sum(i for x,i in random7gen(10000000)) / 10000000.0
1.344606
小开

如果有人能给我关于这个的反馈，那将是很酷的，我使用JUNIT而没有断言模式，因为它在Eclipse中运行起来既简单又快速，我也可以只定义一个main方法。顺便说一句，我假设rand5给出值0-4，加1将使其成为1-5，rand7也是如此…所以讨论应该在解决方案上，它是分布，而不是从0-4或1-5开始…

package random;


import java.util.Random;


import org.junit.Test;


public class RandomTest {




@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}


for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}




public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}




public int rand5() {
return new Random().nextInt(5);
}




}

当我运行它时，我得到这个结果：

Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037

这似乎是一个非常公平的分配，不是吗？

如果我添加rand5（）更少或更多次（其中次数不能被7整除），分布会清楚地显示偏移量。例如，添加rand5() 3次：

Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250

因此，这将导致以下结果：

public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;


}

然后，我可以更进一步：

public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE  = 7;


@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}


for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}




public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;


}




public int rand(int range) {
return new Random().nextInt(range);
}

我尝试用不同的值（ORIGIN为7，DEST为13）替换disRange和原始范围，我得到了这个分布：

Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561

从这里我可以得出的结论是，你可以通过求和原点随机“目标”时间来将任何随机更改为任何其他随机。这将得到一种高斯分布（中间值更有可能，边缘值更不常见）。然而，目的地的模数似乎在这个高斯分布上均匀分布……如果能得到数学家的反馈就太好了……

很酷的是，成本是100%可预测和恒定的，而其他解决方案导致无限循环的概率很小。

小开

首先，我在1点上移动ramdom5（）6次，得到7个随机数。 其次，我将7个数字相加以获得公共总和。 第三，我在7点得到剩余的部分。 最后，我加1得到从1到7的结果。 这种方法给出了从1到7范围内获得数字的相等概率，除了1.1的概率略高。

public int random7(){
Random random = new Random();
//function (1 + random.nextInt(5)) is given
int random1_5 = 1 + random.nextInt(5); // 1,2,3,4,5
int random2_6 = 2 + random.nextInt(5); // 2,3,4,5,6
int random3_7 = 3 + random.nextInt(5); // 3,4,5,6,7
int random4_8 = 4 + random.nextInt(5); // 4,5,6,7,8
int random5_9 = 5 + random.nextInt(5); // 5,6,7,8,9
int random6_10 = 6 + random.nextInt(5); //6,7,8,9,10
int random7_11 = 7 + random.nextInt(5); //7,8,9,10,11


//sumOfRandoms is between 28 and 56
int sumOfRandoms = random1_5 + random2_6 + random3_7 +
random4_8 + random5_9 + random6_10 + random7_11;
//result is number between 0 and 6, and
//equals 0 if sumOfRandoms = 28 or 35 or 42 or 49 or 56 , 5 options
//equals 1 if sumOfRandoms = 29 or 36 or 43 or 50, 4 options
//equals 2 if sumOfRandoms = 30 or 37 or 44 or 51, 4 options
//equals 3 if sumOfRandoms = 31 or 38 or 45 or 52, 4 options
//equals 4 if sumOfRandoms = 32 or 39 or 46 or 53, 4 options
//equals 5 if sumOfRandoms = 33 or 40 or 47 or 54, 4 options
//equals 6 if sumOfRandoms = 34 or 41 or 48 or 55, 4 options
//It means that the probabilities of getting numbers between 0 and 6 are almost equal.
int result = sumOfRandoms % 7;
//we should add 1 to move the interval [0,6] to the interval [1,7]
return 1 + result;
}
小开

这是我的，它尝试从多个rand5()函数调用中重新创建Math.random()，通过使用“加权分数”（？）重新构建单位间隔（Math.random()的输出范围）来重建它。然后使用这个随机单位间隔生成1到7之间的随机整数：

function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var uiRandom=0;
var div=1;
for(var i=0; i<7; i++){
div*=5;
var term=(rand5()-1)/div;
uiRandom+=term;
}
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}

换句话说：我们取一个0-4之间的随机整数（只是rand5()-1），并将每个结果乘以1/5,1/25,1/125，…，然后将它们相加。这类似于二进制加权分数的工作原理；我想相反，我们将其称为五进制（基数5）加权分数：从0-0.999999产生一个数字，作为一系列（1/5）^n项。

修改函数以获取任何输入/输出随机整数范围应该是微不足道的。上面的代码在重写为闭包时可以进行优化。

或者，我们也可以这样做：

function rand5(){
return Math.floor(Math.random()*5)+1;
}
function rand7(){
var buffer=[];
var div=1;
for (var i=0; i<7; i++){
buffer.push((rand5()-1).toString(5));
div*=5;
}
var n=parseInt(buffer.join(""),5);
var uiRandom=n/div;
//return uiRandom;
return Math.floor(uiRandom*7)+1;
}

而不是摆弄构造一个五进制（基数5）加权分数，我们实际上会制作一个五进制数并将其转换为一个分数（0--0.9999……像以前一样），然后从那里计算我们的随机1--7位数。

上面的结果（代码片段#2：每次运行100,000次调用3次）：

1:14263； 2:14414； 3:14249； 4:14109； 5:14217； 6:14361； 7:14387

1:14205； 2:14394； 3:14238； 4:14187； 5:14384； 6:14224； 7:14368

1:14425； 2:14236； 3:14334； 4:14232； 5:14160； 6:14320； 7:14293

小开

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

假设我们的作用域中已经有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()

补充说明

我们可以将这个程序分为两部分：

  1. 循环rand5（）直到我们找到1或2，这意味着我们有1/2的概率在变量twoway中有1或2
  2. 将ans与rand5() + twoway * 5复合，这正是rand10()的结果，如果这不符合我们的需要（1~7），则我们再次运行rand7。

附注：我们不能在第二部分中直接运行一个这时候循环，因为twoway的每个概率都需要是单独的。

但是有一个权衡，因为第一节中的同时循环和返回语句中的递归，这个函数不能保证执行时间，它实际上是无效的。

结果

我做了一个简单的测试来观察我的答案的分布。

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的值的概率，但可能是这个问题的最短答案。

小开 
def rand5():
return random.randint(1,5)    #return random integers from 1 to 5


def rand7():
rand = rand5()+rand5()-1
if rand > 7:                  #if numbers > 7, call rand7() again
return rand7()
print rand%7 + 1

我想这将是最简单的解决方案，但到处都有人建议5*rand5() + rand5() - 5就像http://www.geeksforgeeks.org/generate-integer-from-1-to-7-with-equal-probability/一样。 有人能解释一下rand5()+rand5()-1有什么问题吗？

小开

类似于马丁的回答，但使用熵的频率要低得多：

int rand7(void) {
static int m = 1;
static int r = 0;


for (;;) {
while (m <= INT_MAX / 5) {
r = r + m * (rand5() - 1);
m = m * 5;
}
int q = m / 7;
if (r < q * 7) {
int i = r % 7;
r = r / 7;
m = q;
return i + 1;
}
r = r - q * 7;
m = m - q * 7;
}
}

在这里，我们在0和m-1之间建立一个随机值，并尝试通过添加尽可能多的状态来最大化m而不会溢出（INT_MAX是适合C中int的最大值，或者您可以将其替换为在您的语言和架构中有意义的任何大值）。

然后；如果r落在可被7整除的最大可能区间内，那么它包含一个可行的结果，我们可以将该区间除以7，并将余数作为我们的结果，并将其余值返回到熵池。否则r处于另一个不均匀划分的区间，我们必须丢弃并从该不合适的区间重新启动熵池。

与这里的流行答案相比，它调用rand5()的频率平均约为一半。

为了提高性能，可以将这些分歧分解为琐碎的位处理和LUT。

小开

另一个似乎没有在这里涵盖的答案：

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（含）之间的随机值，结果除以5，给出一个在0到6（含）范围内的新随机值。r从一个很大的偏差开始（r = 3非常有偏差！）但每次迭代都会将该偏差除以5。

这种方法是没有完全一致的；然而，偏差非常小。大约在1/（2**64）的顺序。这种方法的重要之处在于它具有恒定的执行时间（假设rand5()也有恒定的执行时间）。理论上没有担心不幸的调用可能永远迭代选择坏值。

此外，一个讽刺的回答很好的措施（有意或无意，它已被覆盖）：

1-5已经在1-7范围内，因此以下是有效的实现：

int rand7() {
return rand5();
}

问题没有要求均匀分布。

小开

该算法将rand5的调用次数减少到理论上的最小值7/5。通过生成接下来的5个rand7数字来调用它7次。

没有拒绝任何随机位，也没有可能一直等待结果。

#!/usr/bin/env ruby


# random integer from 1 to 5
def rand5
STDERR.putc '.'
1 + rand( 5 )
end


@bucket = 0
@bucket_size = 0


# random integer from 1 to 7
def rand7
if @bucket_size == 0
@bucket = 7.times.collect{ |d| rand5 * 5**d }.reduce( &:+ )
@bucket_size = 5
end


next_rand7 = @bucket%7 + 1


@bucket      /= 7
@bucket_size -= 1


return next_rand7
end


35.times.each{ putc rand7.to_s }
小开 
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}

与所选解决方案不同，该算法将在恒定时间内运行。然而，它确实比所选解决方案的平均运行时间多2次调用rand5。

请注意，这个生成器并不完美（数字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

理论

数字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)
小开
  1. 什么是简单的解决方案？(rand5() + rand5()) % 7 + 1
  2. 什么是减少内存使用或在较慢的CPU上运行的有效解决方案？Yes, this is effective as it calls rand5() only twice and have O(1) space complexity

考虑rand5()给出了从1到5（包括）的随机数。
（1+1）%7+1=3
（1+2）%7+1=4
（1+3）%7+1=5
（1+4）%7+1=6
（1+5）%7+1=7

（2+1）%7+1=4
（2+2）%7+1=5
（2+3）%7+1=6
（2+4）%7+1=7
（2+5）%7+1=1
…

（5+1）%7+1=7
（5+2）%7+1=1
（5+3）%7+1=2
（5+4）%7+1=3
（5+5）%7+1=4
…

等等

小开

我想我有四个答案，两个给出了精确的解决方案就像@Adam Rosenfield那样，但没有无限循环问题，另外两个几乎完美的解决方案，但比第一个更快的实现。

最好的精确解决方案需要7次调用rand5，但让我们继续进行以了解。

方法1-确切

亚当答案的优点是它给出了一个完美的均匀分布，并且有很高的概率（21/25）只需要两次对rand5（）的调用。然而，最坏的情况是无限循环。

下面的第一个解决方案也提供了完美的均匀分布，但总共需要42次对rand5的调用。没有无限循环。

下面是一个R实现：

rand5 <- function() sample(1:5,1)


rand7 <- function()  (sum(sapply(0:6, function(i) i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6)) %% 7) + 1

对于不熟悉R的人，这里有一个简化版本：

rand7 = function(){
r = 0
for(i in 0:6){
r = r + i + rand5() + rand5()*2 + rand5()*3 + rand5()*4 + rand5()*5 + rand5()*6
}
return r %% 7 + 1
}

rand5的分布将被保留。如果我们进行数学运算，循环的7次迭代中的每一次都有5^6种可能的组合，因此可能组合的总数为(7 * 5^6) %% 7 = 0。因此我们可以将生成的随机数划分为7个相等的组。有关此的更多讨论，请参阅方法二。

以下是所有可能的组合：

table(apply(expand.grid(c(outer(1:5,0:6,"+")),(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)


1     2     3     4     5     6     7
15625 15625 15625 15625 15625 15625 15625

我认为这很直接地表明Adam的方法会运行得更快。在Adam的解决方案中有42次或更多次调用rand5的概率非常小（(4/25)^21 ~ 10^(-17)）。

方法2-不完全

现在是第二个方法，它几乎是统一的，但需要6次调用rand5：

rand7 <- function() (sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

以下是一个简化版本：

rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return r %% 7 + 1
}

这本质上是方法1的一次迭代。如果我们生成所有可能的组合，以下是结果计数：

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6),1,sum) %% 7 + 1)


1    2    3    4    5    6    7
2233 2232 2232 2232 2232 2232 2232

一个数字将再次出现在5^6 = 15625试验中。

现在，在方法1中，通过将1到6相加，我们将数字2233移动到每个连续的点。因此组合的总数将匹配。这是有效的，因为5^6%%7=1，然后我们做7个适当的变化，所以（7*5^6%%7=0）。

方法3-精确

如果方法1和2的参数被理解，方法3如下，并且只需要7次调用rand5。在这一点上，我觉得这是精确解决方案所需的最小调用次数。

下面是一个R实现：

rand5 <- function() sample(1:5,1)


rand7 <- function()  (sum(sapply(1:7, function(i) i * rand5())) %% 7) + 1

对于不熟悉R的人，这里有一个简化版本：

rand7 = function(){
r = 0
for(i in 1:7){
r = r + i * rand5()
}
return r %% 7 + 1
}

rand5的分布将被保留。如果我们进行数学运算，循环的7次迭代中的每一次都有5种可能的结果，因此可能组合的总数为(7 * 5) %% 7 = 0。因此我们可以将生成的随机数分成7个相等的组。有关更多讨论，请参阅方法一和方法二。

以下是所有可能的组合：

table(apply(expand.grid(0:6,(1:5)),1,sum) %% 7 + 1)


1 2 3 4 5 6 7
5 5 5 5 5 5 5

我认为这很直接地表明Adam的方法仍然会运行得更快。在Adam的解决方案中有7次或更多次调用rand5的概率仍然很小（(4/25)^3 ~ 0.004）。

方法4-不完全

这是第二种方法的一个小变体。它几乎是统一的，但需要7次对rand5的调用，这是方法2的额外一次：

rand7 <- function() (rand5() + sum(sapply(1:6,function(i) i*rand5())) %% 7) + 1

以下是一个简化版本：

rand7 = function(){
r = 0
for(i in 1:6){
r = r + i*rand5()
}
return (r+rand5()) %% 7 + 1
}

如果我们生成所有可能的组合，这里是结果计数：

table(apply(expand.grid(1:5,(1:5)*2,(1:5)*3,(1:5)*4,(1:5)*5,(1:5)*6,1:5),1,sum) %% 7 + 1)


1     2     3     4     5     6     7
11160 11161 11161 11161 11161 11161 11160

两个数字将在5^7 = 78125试验中少出现一次。对于大多数目的，我可以忍受。

小开

这是我想出的答案，但这些复杂的答案让我觉得这是完全关闭/：））

import random


def rand5():
return float(random.randint(0,5))


def rand7():
random_val = rand5()
return float(random.randint((random_val-random_val),7))


print rand7()
小开

来自扩展浮点范围的链接。这个更有趣。而不是我如何得出结论，我突然想到，对于给定的随机整数生成函数f with“base”b（在这种情况下为4，我会告诉为什么），它可以像下面这样扩展：

(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)

这将把随机生成器转换为浮点生成器。我将在这里定义2个参数b和p。虽然这里的“基数”是4，b实际上可以是任何东西，它也可以是无理数等。p，我称之为精度是您希望浮点生成器的粒度程度。将其视为每次调用rand7对rand5的调用次数。

但是我意识到，如果你将b设置为base+1（在这种情况下是4+1=5），它是一个最佳点，你会得到一个均匀分布。首先摆脱这个1-5生成器，它实际上是rand4（）+1：

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

要到达那里，您可以将rand4替换为rand5()-1

下一步是将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 INCLUSIVE）转换为任何其他浮点范围，然后将其降级为整数。这里我们的基数是4，因为我们处理的是rand4，因此值b=5将给你一个均匀分布。随着b增长到4，你将开始在分布中引入周期性间隙。我测试了2到8的b值，每个值3000点，与javascript的原生Math.random相比，在我看来甚至比原生更好：

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

对于上面的链接，单击分布顶部的“bin”按钮以减小分箱大小。最后一个图是原生Math.random，第四个图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
小开 

// returns random number between 0-5 with equal probability
function rand5() {
return Math.floor(Math.random() * 6);
}


// returns random number between 0-7 with equal probability
function rand7() {
if(rand5() % 2 == 0 && rand5() % 2 == 0) {
return 6 + rand5() % 2;
} else {
return rand5();
}
}


console.log(rand7());

小开

这里有一个解决方案，试图尽量减少对rand5（）的调用次数，同时保持实现简单高效；特别是，它不像Adam Rosenfield的第二个答案那样需要任意的大整数。它利用了23/19=1.21052……是log（7）/log（5）=1.20906……的良好有理近似这一事实，因此我们可以通过拒绝采样从{1，…，5}的23个随机元素中生成19个{1，…，7}的随机元素，拒绝概率很小。平均而言，下面的算法每次调用rand7（）需要大约1.266次对rand5（）的调用。如果rand5（）的分布是均匀的，那么rand7（）也是均匀的。

uint_fast64_t pool;


int capacity = 0;


void new_batch (void)
{
uint_fast64_t r;
int i;


do {
r = 0;
for (i = 0; i < 23; i++)
r = 5 * r + (rand5() - 1);
} while (r >= 11398895185373143ULL);  /* 7**19, a bit less than 5**23 */


pool = r;
capacity = 19;
}


int rand7 (void)
{
int r;


if (capacity == 0)
new_batch();


r = pool % 7;
pool /= 7;
capacity--;


return r + 1;
}
小开

对于范围[1,5]到[1,7]，这相当于用5面模具滚动7面模具。

然而，这不能在不“浪费”随机性的情况下完成（或在最坏的情况下永远运行），因为7的所有素数因子（即7）都不除5。因此，能做的最好的是使用拒绝采样来任意接近没有“浪费”的随机性（例如通过批处理多个5面模具卷，直到5^n“足够接近”7的幂）。这个问题的解决方案已经在其他答案中给出了。

更一般地说，用p来滚动k的算法将不可避免地“浪费”随机性（在最坏的情况下永远运行），除非根据B. Kloeckner在《用骰子模拟骰子》中的引理3，“每个除以k的素数也除以p”。例如，以更实际的情况为例，p是2的幂，k是任意的。在这种情况下，这种“浪费”和不确定的运行时间是不可避免的，除非k也是2的幂。

小开

Python：有一个简单的两行答案，它使用了空间代数和模的组合。这不是直观的。我对它的解释很混乱，但是正确的。

Knowing that 5*7=35 and 7/5 = 1 remainder 2. How to guarantee that sum of remainders is always 0? 5*[7/5 = 1 remainder 2] --> 35/5 = 7 remainder 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

提交答案