Правильна ли эта реализация языка Фишера-Йейтса на С? - PullRequest
Новая
       7

Правильна ли эта реализация языка Фишера-Йейтса на С?

10 голосов
/ 27 июля 2010

Вот 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;   
  }
}

1 Ответ

27 голосов
/ 28 июля 2010

Во-первых, вы должны извлечь код для генерации случайного числа, которое одинаково распределено между 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!.

...