给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。


当前回答

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

其他回答

这类似于@RobMcAfee,除了我使用魔术数字而不是2维数组。

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

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

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

int rand7()
{
    int zero_one_or_two = ( rand5() + rand5() - 1 ) % 3 ;
    return rand5() + zero_one_or_two ;
}

简单的解决方案已经被很好地覆盖了:为一个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

为什么这行不通?除了对rand5()的额外调用之外?

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

i = i % 7 + 1;