使用给定的随机数发生器打印1-100的最有效算法

Question

我们得到了一个随机数生成器 RandNum50 它在1-50范围内均匀地产生一个随机整数。我们可以仅使用此随机数生成器以随机顺序生成和打印所有整数从1到100。每个数字都必须完全出现一次，并且在任何位置发生的任何数字的概率都必须相等。

最有效的算法是什么？

Answer 1

我以为（所以可能是错误的:-)这个$ o（n^2）$解决方案 渔民yates洗牌. 。为了保持统一分配 好近似 （请参阅下面的编辑部分）在每次迭代中，您都可以使用此技巧来产生一个值 krand $ 0 $和$ k-1 $之间：

 // return a random number in [0..k-1] with uniform distribution
 // using a uniform random generator in [1..50]
 funtion krand(k) {    
   sum = 0
   for i = 1 to k do sum = sum + RandNum50() - 1
   krand = sum mod k
 }

Fisher-Yates算法变为：

arr : array[0..99]
for i = 0  to 99 do arr[i] = i+1; // store 1..100 in the array
for i = 99 downto 1 {
  r = krand(i+1)  // random value in [0..i]
  exchange the values of arr[i] and arr[r]
}
for i = 0 to 99 do print arr[i]

编辑：

正如埃里克（Erick）指出的那样 krand 上面的功能不会返回真正统一的分布。还有其他方法可以用来获得更好（任意更好）和更快的近似方法。但是（据我所知）获得真正统一分配的唯一方法是使用 拒绝采样: ：选择$ m = lceil log_2（k） rceil $随机位，如果获得的数字$ r $小于$ k $返回，则会生成另一个随机数；可能的实施：

function trulyrand(k) {
    if (k <= 1) return 0
    while (true) { // ... if you're really unlucky ...
      m = ceil(log_2 (k) ) // calculate m such that k < 2^m
      r = 0  // will hold the random value
      while (m >= 0) {  // ... will add m bits        
        if ( rand50() > 25 ) then b = 1 else b = 0   // random bit
        r = r * 2 + b  // shift and add the random bit
        m = m - 1
      }      
      if (r < k) then return r  // we have 0<=r<2^m ; accept it, if r < k
    }
}

Answer 2

由于其他人给出了涉及不确定数量偏差的近似解决方案和解决方案，因此证明没有这样的算法保证只需要有限数量的算法 RandNum50() 电话？

正如其他人所指出的那样，按随机顺序打印数字等同于打印这些数字的随机排列。有100！在这些排列中，因此必须以概率$ frac {1} {100！} $输出任何特定的排列。

但是，如果我们知道我们的算法最多使用$ k $来调用 RandNum50 对于一些$ k $，然后我们可以说：首先，填写那些少于$ k $调用的计算路径 RandNum50 要进行其他虚拟电话（即返回值无关紧要的呼叫），以便所有计算路径恰好是$ k $调用。 $ k $的任何给定序列来自我们的电话 RandNum50 必须产生一些输出排列，因此我们可以构建一个“结果表”，该表将我们调用的结果映射到任何给定的序列$（R_1，R_2， ldots，r_k）$中，从我们的调用中映射到特定的输出置换中。由于这些结果中的每一个都有可能（每个结果都有概率$ displayStyle frac {1} {1} {50^k} $），因此从我们的算法中获取任何特定排列的概率必须为$ displayStyle frac {c} {50^k} $对于某些$ c $。但是$ displayStyle frac {1} {100！} $不能来自此表格，因为$ 100！$不为任何$ k $分配$ 50^k $（例如，3个划分$ 100！$，但可以't除以任何数量的$ 50^k $）。这意味着不可能将结果分布到随机数呼叫上可以产生均匀的排列。

Answer 3

先前的解决方案不是最佳的。复杂性恰好是$ n log n + o（1）$ in Randnum50，并在某些详细范围内进行了描述 这里, ，用作随机位的来源（如VOR所建议）：

if ( rand50() > 25 ) then b = 1 else b = 0   // random bit

基本想法是，如果您在$ 1 $和$ n！$之间生成制服，然后使用，然后使用 阶基碱分解, ，而不是生成一系列制服，最多可达$ 1 $，然后是$ 2 $，然后是$ 3 $等，$ n $。实际上，正如我在帖子中提到的那样，我提交了一篇论文的话题！

如果您不知道如何从随机位生成制服，那么您也可以以这种方式直接生成统一的近似值（这相当于Vor的“ Trulyrand”，但更快）：

P = (RandNum50()-1) + (RandNum50()-1)*50^1 + (RandNum50()-1)*50^2 + ...

尽可能走。这是在基本$ 50 $中开发$ p $。然后，只需截断$ p $，即，$ q = p mod n $，在您的情况下$ n = 100！$。该值不是完全随机的，而是经常使用的均匀性的度量。或者，正如VOR所建议的那样，如果$ p> n $，您可以拒绝。然后，有了这个值，您可以按照阶乘基础扩展如前所述 邮政.

Answer 4

我尚未进行分析以确认这将是多么统一（或不统一），并且可以调整为真正的洗牌，但是您可以从一个起始数组中选择 iTh索引= i + 1, ， 这 (k + RandNum50() + RandNum50() - 1) mod (100 - k) 索引，删除，用于 k = 0..99?

这“推”了 RandNum50() + RandNum50() 均匀分配。

_{我很确定这不是我所说的那样正确，因为从第一选择中无法获得0索引（1），而且我无法快速看到替代的1..50 + 1..50调整0 ..99。}

更新

为了解决我注意到的问题，我有效地使用了 RandNum100 如问题评论中提到的，以随机初始化第一个 k 抵消。

这会产生一个分布，前面有明显的波。

我没有前进1我使用了另一个 RandNum50 首先增加 k. 。这对我来说是足够随机的结果，但是它仍然不是“真正的”随机，如果将K更改为2，可以很容易地看到。

测试VB.NET代码 我符合任何K。