生成[0..n-1]范围内的m个不同的随机数

一尘不染

生成[0..n-1]范围内的m个不同的随机数

algorithm

我有两种方法可以生成[0..n-1]范围内的m个不同的随机数

方法1：

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

方法2：

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

当n远大于m时，第一种方法更有效，否则，第二种方法更有效。但是“更大”不是一个严格的概念，对吗？:)

问题： 应该使用n和m的哪个公式来确定method1或method2的效率更高？（根据对运行时间的数学期望）

阅读 210

2020-07-28

共1个答案

一尘不染

纯数学：
让我们计算rand()两种情况下函数调用的数量并比较结果：

情况1： 让我们看看i = k已经选择了k个数字时对step调用的数学期望。通过一次rand()呼叫获得号码的概率等于p = (n-k)/n。我们需要知道这样的通话数量的数学期望，这会导致获得我们还没有的号码。

使用1call 获得它的概率为p。使用2电话- q * p，其中q = 1 - p。在一般情况下，在n致电后准确获得的可能性为(q^(n-1))*p。因此，数学期望为
Sum[ n * q^(n-1) * p ], n = 1 --> INF。该总和等于1/p（由Wolfram alpha证明）。

因此，在该步骤上，i = k您将执行1/p = n/(n-k)该rand()函数的调用。

现在让我们对其进行整体总结：

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T-数量rand方法1中调用
这里T = Sum[ 1/(n - k) ], k = 0 --> m - 1

情况2：

在大多数实现中，这rand()称为内部random_shuffle n - 1时间。

现在，要选择方法，我们必须比较这两个值：n * T ? n - 1。
因此，要选择适当的方法，请T按照上述方法进行计算。如果T < (n - 1)/n最好使用第一种方法。否则，请使用第二种方法。

2020-07-28