c++ - 生成[0,n-1]区间内的k个唯一随机数？

Question

如何生成[0,n-1]区间内的k个唯一随机数？

我使用了以下代码:

for( int i = 0 ; i < n ; ++i ){
   a[i]=i;
}

std::random_shuffle( a, a+n ) ;
for(int i=0;i<k;++i){
  ra[i]=a[i];
}

取前 k 个元素。

任何人都可以向我推荐一种更快的方法吗？

std::random_shuffle: http://www.cplusplus.com/reference/algorithm/random_shuffle/

Answer 1

对于较小的 n 值，您的方法非常适合。当然，您可以手动混合数组的元素，但这不太可能更快。

对于较大的值，您可以使用 Linear Congruential Generator :

r[n + 1] = (a * r[n] + c) % m;

其中 m(模数)等于您的 n。为了最大化生成序列的长度，您在选择值 a 和 c 时应该遵循一些规则(有关详细信息，请参见上面的链接)。

当然，k 应该小于 n。