代码之家 › 专栏 › 技术社区 › MikeRand

Fisher Yates Shuffle的C实现是否正确?

shuffle c

10

MikeRand · 技术社区 · 15 年前

下面是fisher-yates的C实现,我想在一个deck-shuffling例程中使用它。我这样做是否正确(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;   
  }
}

1 回复 | 直到 8 年前

1

27

Roland Illig 15 年前

首先,您应该提取代码来生成一个随机数,该随机数在 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 函数必须是 n! .