是费雪耶茨这个C实现的洗牌是否正确？ [英] Is this C implementation of Fisher-Yates shuffle correct?

问题描述

下面是费雪耶茨的C实现，我想在甲板洗牌日常使用。我在正确的做这个（N =长数组）？

Here's a C implementation of Fisher-Yates that I want to use in a deck-shuffling routine. Am I doing this correctly (n = length of array)?

注：do-whil​​e循环试图纠正模偏置（此处一>）。它增加了一些开销的程序，如果你不关心低位偏见可能被淘汰。

Note: The do-while loop attempts to correct for the modulo bias (see here). It adds a bit of overhead to the procedure and could be eliminated if you don't care about the low-bit bias.

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;   
  }
}

谢谢，

迈克

推荐答案

首先，你要提取code，用于生成的同样 0 之间分布的随机数（含）和 N （不含）到一个单独的功能。这是工作的一个很好的任务，你将需要在其他地方也一样。

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.

第二，我不会把函数srand 中的随机功能，但取决于呼叫者初始化随机数发电机。这样，你可以洗牌甲板不止一次在第二。

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.

三，你应该做的测试 J＆GT; UPPER_BOUND 按分割之前，我+ 1 。这是不可能的， I 将永远不会接近 RAND_MAX 。

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;
  }
}

要检查这是否实施可能是正确的，你需要确保你问 LOG2的随机数发生器（N！）随机性位。换句话说，该产品所有的 N s表示到 rand_int 函数必须是 N！。

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!.

这篇关于是费雪耶茨这个C实现的洗牌是否正确？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！