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

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

(我剽窃了亚当·罗森菲尔德的答案，使其运行速度提高了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()

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

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

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

这个解决方案不浪费任何熵，并给出了范围内第一个可用的真正随机数。随着每一次迭代，得不到答案的概率可证明地降低了。在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;
}

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

对于范围[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的幂。