生成唯一随机数数组

Question

我正在编写一个函数，该函数的作用是使用从0到n（其中n是传递给函数的参数）的随机数填充数组，但数组中的所有数字都应该是唯一的。我基本上需要对从0到n的数字数组进行随机排序。

我在这里找到了答案：C编程语言中整数数组中的唯一随机数 并使用用户建议的“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的数字数组。我该如何生成真正的唯一随机数序列。

- Ach113

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找到更好的方法。

- Jean-François Fabre

---

我意识到这可能是问题所在，但由于我想从0到N生成N个数字而不是从0到M生成N个数字，所以我认为N=M会起作用。我需要使用另一个算法吗？ - Ach113

我已经编辑过了。实际上，你只需要使用另一个问答网站。 - Jean-François Fabre

Answer 2

我基本上需要将从0到n的数字数组洗牌。 那么为什么不直接 这样做 呢？ Knuth算法用于选择指定范围的随机子集，按升序排列。 它是随机选择 哪个子集，而不是元素的顺序，但只有一个子集包含所有元素。 无论如何，如果您想要它们随机排序，那么仍然需要对Knuth算法的结果进行洗牌，这使您回到了起点。

- John Bollinger