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

0まず、 （包括的）とn（排他的）の間で均等に分散される乱数を生成するためのコードを抽出して、別の関数にする必要があります。これは、他の場所でも必要になる素晴らしい作業です。

srand次に、関数内では呼び出しませんがshuffle、乱数ジェネレーターの初期化は呼び出し元に依存します。そうすれば、1秒間に複数回デッキをシャッフルできます。

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に与えられたすべてのsの積はである必要があります。rand_intn!

于 2010-07-27T21:27:11.853 に答える