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

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没有可能的一次性值，我还没有找到它。

什么是简单的解决方案?(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 .

等等

如果有人能就这一点给我反馈，那就太酷了，我使用了没有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;
}

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

我想我有四个答案，两个给出了像@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次试验中，有两个数字会少出现一次。在大多数情况下，我可以接受。