11

这是我想在洗牌程序中使用的 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;   
  }
}
4

1 回答 1

28

First, you should extract the code for generating a random number that's equally distributed between 0 (inclusive) and n (exclusive) to a separate function. That's a nice task of work that you will need elsewhere, too.

Second, I would not call srand inside the shuffle function but depend on the caller on initializing the random number generator. That way you can shuffle a deck more than once in a second.

Third, you should do the test for j > upper_bound before dividing by i + 1. It's unlikely that i will ever be near 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;
  }
}

To check whether this implementation may be correct, you need to ensure that you asked the random number generator for log2(n!) bits of randomness. In other words, the product of all the ns given to the rand_int function must be n!.

于 2010-07-27T21:27:11.853 回答