c - 如何创建数组的随机排列？

Question

我用 C 语言编写了这个函数，我希望它创建一个随机排列或从 1 到 n 的数字列表。我很难让它没有重复的数字。所以如果你有 n = 4，我希望它返回一个随机数组，每个数组只包含一次 1-4，例如:{1,3,4,2}

int* random(int n) 
{
    int* r = malloc(n * sizeof(int));
    // initial range of numbers
    for(int i=0;i<n;++i){
        r[i]=i+1;
    }
    // shuffle
    for (int i = 1; i <= n; ++i){
        int j = rand() % i;
        r[i] = r[j];
        r[j] = i;
  }
  return r;
}

Answer 1

将第二个 for 循环更改为:

for (int i = n-1; i >= 0; --i){
    //generate a random number [0, n-1]
    int j = rand() % (i+1);

    //swap the last element with element at random index
    int temp = r[i];
    r[i] = r[j];
    r[j] = temp;
}

这是 Fisher-Yates 改组算法。我听说使用 rand() % n 不会均匀分布，您已被警告过。

如果您想每次都生成唯一的排列，您可以将生成的排列存储在Dictionary 或Hashmap 中，然后每次返回时查找。我认为 C 没有内置的，但应该有可用的库。