Fisher-Yates shuffle 的 C 实现正确吗？

Question

这是 Fisher-Yates 的 C 实现，我想在牌组洗牌例程中使用它。我这样做是否正确（n = 数组长度）？

注意：do-while 循环尝试纠正模偏差（请参阅 在这里）。它会增加程序的一些开销，如果您不关心低位偏差，则可以将其消除。

void shuffle(int *array, int n) {

  int i, j, tmp, upper_bound;

  srand(time(NULL));

  for (i = n - 1; i > 0; i--) {

    upper_bound = RAND_MAX - ((RAND_MAX % (i + 1)) + 1);

    do {
      j = rand() % (i + 1);
    } while (j > upper_bound);

    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;   
  }
}

Answer 1

首先，您应该将用于生成在 0（包含）和 n（不包含）之间均匀分布的随机数的代码提取到单独的函数中。这是一项很好的工作任务，你在其他地方也需要这样做。

其次，我不会在 shuffle 函数内调用 srand ，而是依赖调用者来初始化随机数生成器。这样你就可以在一秒钟内多次洗牌。

第三，您应该对 j > 进行测试。 upper_bound，然后除以i + 1。 i 不太可能接近 RAND_MAX。

static int rand_int(int n) {
  int limit = RAND_MAX - RAND_MAX % n;
  int rnd;

  do {
    rnd = rand();
  } while (rnd >= limit);
  return rnd % n;
}

void shuffle(int *array, int n) {
  int i, j, tmp;

  for (i = n - 1; i > 0; i--) {
    j = rand_int(i + 1);
    tmp = array[j];
    array[j] = array[i];
    array[i] = tmp;
  }
}

要检查此实现是否正确，您需要确保向随机数生成器询问 log2(n!) 位随机性。换句话说，提供给 rand_int 函数的所有 n 的乘积必须是 n!。