这个Fisher-Yates的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(不包括)之间平均分配给单独的函数.这也是你在其他地方需要的一项很好的工作任务.

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

第三,你应该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!)随机性位.换句话说,n给予rand_int函数的所有s 的乘积必须是n!.