生成唯一随机数的数组

Question

我正在编写一个函数，它应该用0到n的随机数填充数组（其中n是函数的参数），但数组中的所有数字都应该是唯一的。我基本上需要将数字数组从0改为n

我在这里找到了这个答案：Unique random numbers in an integer array in the C programming language

并使用了用户建议的“Knuth算法”：

void generate_random_array(int count)
{
  int in, im;

  im = 0;
  srand(time(NULL));

  for (in = 0; in < count && im < count; ++in) {
    int rn = count - in;
    int rm = count - im;
    if (rand() % rn < rm) random_array[im++] = in; 
  }
}

但是这个函数根本不会为我生成随机数，它只是创建一个从0到count的数字数组。如何生成唯一数字的实际随机序列。

Answer 1

在您引用的答案中，该算法的C实现示例如下：

#define M 10
#define N 100

int in, im;

im = 0;

for (in = 0; in < N && im < M; ++in) {
  int rn = N - in;
  int rm = M - im;
  if (rand() % rn < rm)    
    /* Take it */
    vektor[im++] = in + 1; /* +1 since your range begins from 1 */
}

Knuth算法。这是一种非常简单的算法，其复杂度为O（N）（即数值范围），这意味着当M接近N时它最有用。

但你设置的M == N不是很接近但是相等

所以rn和rm的初始值是相同的。所以这不能使算法正常工作，因为：

whatever % rn < rm

总是如此，就像345436 % 22 < 22自从a % b < b一样。

因此测试始终为真，每次都存储整数，因此in和im每次增加1，依此类推。

我基本上需要将数字数组从0改为n

这个算法并不是你所需要的：它根本不会对数组进行混洗，它会通过从不断增加的值中选择一个来产生有序的随机数（因此，唯一）。像你一样限制值会强制算法发出范围的所有值。

你会有更好的运气与Shuffle array in C

Answer 2

我基本上需要将数字数组从0改为n

那么为什么不do that？ Knuth算法用于选择指定的整个范围的随机子集，它以升序发出。它是随机的子集，而不是元素的顺序，但只有一个子集包含所有元素。在任何情况下，如果你想要它们是随机顺序，那么你仍然需要改变Knuth算法的结果，这样你就可以准确地离开你的位置了。