这里允许作业题吗?

这个函数进行粗略的“以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

编辑:这并不奏效。误差约为千分之二(假设是完美的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就增加一个数量级

BTW:上面的误差表不是通过采样产生的，而是通过以下递归关系产生的:

P [x,n]是给定n次调用rand5，输出=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;
}    

假设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

(我剽窃了亚当·罗森菲尔德的答案，使其运行速度提高了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中所能产生的最大值。如果到目前为止的结果在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)算法并测试和评估它(分布和速度)。只需将代码放入“Rand7WithRand5”方法并运行代码片段。

一些观察:

亚当·罗森菲尔德(Adam Rosenfield)的算法并不比我的算法分布得更好。不管怎样，两种算法的分布都很糟糕。 本机Rand7(随机的。Next(1,8))完成，因为它在大约200+迭代中生成了给定间隔内的所有成员，Rand7WithRand5算法的顺序为10k(约30-70k) 真正的挑战不是编写从Rand(5)生成Rand(7)的方法，而是生成几乎均匀分布的值。

下面是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，这样我就可以摆弄它们，我想我把它贴在这里，希望它对外面的人有用，而不是花很长时间来拼凑。

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

保持平均分配;而且 不需要牺牲随机序列中的任何元素。

这两个问题都是简单的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;
}

How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. That's what this code is doing: the i and j indexes randomly select a location on the dart board, and if we don't get a good result, we keep throwing darts.

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

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

最简单的分析方法是将流I和O分别视为5元数和7元数。这是通过主答案的思想来实现的，即取流a1, a2, a3，…- > a1 + a2 + 5 * 5 ^ 2 * a3 + . .流O也是如此。

然后如果我们取长度为m的输入流的一段，选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)也就是。82米。

上述分析的难点是方程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)是由大小为X的均匀输入导出的随机(1-7)整数的输出序列的平均长度，并假设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。

然后机械师》(5 ^ m) = nx (7 ^ n) / (7 ^ n + s) = o (n + 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)。

整个问题取决于5^m的7位数字对不同m值的分布。

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

这个答案更像是一个从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()的调用次数，以最大限度地利用随机性。也就是说，如果你认为随机性是一种宝贵的资源，我们就会尽可能多地利用它，而不丢弃任何随机比特。这个答案也与伊万的回答中的逻辑有一些相似之处。

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位整数也不会增加太多。

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

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 is 15625 7 times 2232 is 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的调用。与其他解决方案一样，它有小概率会循环很长时间。

上面引用了一些优雅的算法，但这里有一种方法可以接近它，尽管它可能是迂回的。我假设的值是从0开始的。

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

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

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

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

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的几率较低，然而，如果你只是想要一个快速和可读的解，这是一种方法。

只要没有剩下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

需要事先播种。

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范围内，就像预期的近似高斯分布一样)。

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

也许亚当·罗森菲尔德会好心地评论一下?

我(天真?)的想法是这样的:

积累rand5，直到有足够的随机位形成rand7。这最多需要2兰特。为了得到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亿次试验的结果。

'Real' rand函数mod 5或7

rand5 ： 平均=1.999802 0：20003944 1：19999889 2：20003690 3：19996938 4：19995539 Rand7 ： 平均=3.000111 0：14282851 1：14282879 2：14284554 3：14288546 4：14292388 5：14288736 6：14280046

我的边缘7

平均数看起来不错，数字分布也不错。

Randt ： 平均=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

3次调用Rand5，平均125次中只重复6次。

把它想象成一个5x5x5的3D数组，一遍又一遍地填满1到7，还有6个空格。重新滚动空白。rand5调用在该数组中创建一个以5为基数的三位索引。

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;

这个怎么样

rand5 () % + rand5 (2) + 2 (2) % + rand5 rand5 () (2) % + rand5 % + rand5 (2) 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之间的整数。如果我没记错的话，得到7个结果中的任何一个的概率都是16/112。

假设rand给予所有位相同的权重，然后用上界进行掩码。

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

Rand(5)只能返回:1b, 10b, 11b, 100b, 101b。有时候你只需要考虑设置2位。

以下是我的发现:

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

然后我们得到1~7的范围，这是我们正在寻找的Random7。

为什么不除以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

这不是很容易吗?

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

进口随机 def rand5 (): 返回random.randint(1、5) def rand7 (): 返回((rand5() -1) * rand5()) %7)+1

int rand7()
{
    return ( rand5() + (rand5()%3) );
}

rand5() -返回1-5之间的值 rand5()%3 -返回0-2之间的值 所以，当加起来时，总价值将在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]

从我读到的许多答案中，它们要么提供了一致性，要么提供了暂停保证，但不能同时提供(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 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]

js小提琴

我觉得你们都想多了。难道这个简单的解决方案行不通吗?

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

给定一个生成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

下面是一个利用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

如果有人能就这一点给我反馈，那就太酷了，我使用了没有assert模式的JUNIT，因为在Eclipse中运行它很容易，也很快速，我也可以只定义一个主方法。顺便说一下，我假设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);
}

我尝试用不同的值替换destRange和originRange(甚至ORIGIN为7,DEST为13)，我得到了这样的分布:

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:运行3次，每次100,000次调用):

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

解释

我们可以把这个程序分成两个部分:

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

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有什么问题吗

与Martin的答案相似，但却很少抛弃熵:

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(包括4)之间的随机值，结果除以5，得到一个0到6(包括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;
}

与选定的解决方案不同，该算法将在常数时间内运行。然而，它对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)

什么是简单的解决方案?(rand5() + rand5()) % 7 + 1 减少内存使用或在较慢的CPU上运行的有效解决方案是什么?是的，这是有效的，因为它只调用rand5()两次，空间复杂度为O(1)

考虑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，但为了理解，让我们继续。

方法一:精确

Adam的答案的优点在于它给出了一个完美的均匀分布，并且只需要两次调用rand5()的概率非常高(21/25)。然而，最坏的情况是无限循环。

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

下面是一个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的解中有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)。

方法三:精确

如果理解了方法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的解中有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，以“基数”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

//返回0-5之间概率相等的随机数 函数rand5() { return Math.floor(Math.random() * 6); ｝ //返回0-7之间概率相等的随机数 函数rand7() { If (rand5() % 2 == 0 && rand5() % 2 == 0) { 返回6 + rand5() % 2; }其他{ 返回rand5 (); ｝ ｝ console.log (rand7 ());

Here is a solution that tries to minimize the number of calls to rand5() while keeping the implementation simple and efficient; in particular, it does not require arbitrary large integers unlike Adam Rosenfield’s second answer. It exploits the fact that 23/19 = 1.21052... is a good rational approximation to log(7)/log(5) = 1.20906..., thus we can generate 19 random elements of {1,...,7} out of 23 random elements of {1,...,5} by rejection sampling with only a small rejection probability. On average, the algorithm below takes about 1.266 calls to rand5() for each call to rand7(). If the distribution of rand5() is uniform, so is 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面骰子的算法将不可避免地“浪费”随机性(并且在最坏的情况下永远运行)，除非“每个质数能除k也能除p”，根据B. Kloeckner的“用骰子模拟骰子”中的引理3。例如，举一个更实际的例子，p是2的幂，k是任意的。在这种情况下，这种“浪费”和无限的运行时间是不可避免的，除非k也是2的幂。

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