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不均匀分布，你已经被警告过。

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

Answer 2

这可能不是最有效的方法，但是由于您已经在开始时填充了数组，因此您可以循环遍历元素并为每个元素选择一个 1 到 n 范围内的随机索引，然后交换该项目：

int* random(int n) 
{
    int* r = malloc(n * sizeof(int));
    for(int i=0;i<n;++i){
        r[i]=i+1;
    }
    for(int i=0; i<n; ++i){
        int randIdx = rand() % n;
        // swap r[i] with r[randIdx]
        int t = r[i];
        r[i] = r[randIdx];
        r[randIdx] = t;
    }
  return r;
}

我不知道这是否是最有效的，或者即使它提供了最好的分布。但这很简单:-)

Answer 3

如果你想重复以上几次，并且你不想每次都得到相同的排列，只需在开头添加以下行：

srand((unsigned)time(NULL));