在C中随机播放一个int数组 - 没有while循环

Question

我想要对一组int进行Shuffle，对数组进行排序，其大小为n，值为1 - n。我只是想避免使用while循环以确保rand（）不会给我相同的索引。代码看起来像这样的somthin：

void shuffleArr(int* arr, size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i < n - 1; ++i)
  {
    while((newIndx = i + rand() % (n - i)) == i);

    swap(i, newIndx, arr);
  }
}

for循环一直持续到n-1，因此例如在最后一次运行中它有50/50的机会等于i。我想避免这个想法。

Answer 1

如果您正在搜索1 ... n范围内的随机数但不包括该范围内的某个数字m，则可以获得范围1 ...（n-1）中的随机数，并且对于任何结果> = m add 1到值。

如果您正在寻找对有限列表进行混洗的算法的解释，请在此处查看Fisher-Yates：https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

Answer 2

这是解决方案，它涉及两者。

void Shuffle(int[] arr, size_t n)
{
  int newIndx = 0;
  int i = 0;

  for(; i < n - 2; ++i)
  {
    newIndx = i + rand() % (n - i);
    if(newIndx == i)
    {
      ++newIndx;
    }

    swap(i, newIndx, arr);
  }
}

没有必要循环，直到有一个好（随机数！= i），因为它与newIndx的if +增量固定。