c - Fisher-Yates shuffle 的这个 C 实现是否正确？

Question

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

注意:do-while 循环尝试纠正模偏差(参见 here )。它为过程增加了一些开销，如果您不关心低位偏差，则可以将其消除。

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，而是依赖调用者初始化随机数生成器。这样你就可以在一秒钟内多次洗牌。

第三，在除以 i + 1 之前，您应该对 j > upper_bound 进行测试。 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!。