Является ли эта реализация C перетасовкой Фишера-Йейтса правильной?

Вот реализация Фишера-Йейтса на 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;   
  }
}

c shuffle
person MikeRand    schedule 27.07.2010    source источник
comment
Мне просто пришло в голову, что int lim = RAND_MAX-i; ... } while (j>upper_bound && --lim); может быть подходящим способом поймать это может никогда произойти случай повторяющихся случайных чисел вне допустимого диапазона.   -  person nategoose    schedule 27.07.2010

Ответы (1)


arrow_upward
28
arrow_downward

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

person Roland Illig    schedule 27.07.2010
comment
+1 за комментарий к раздаче. Это также проблема безопасности, если внешние пользователи вашего кода могут предсказывать/влиять на вашу перетасовку, контролируя время. - person Darron; 28.07.2010
comment
Что означает, что вызывающая сторона инициализирует случайное число? Это как в зависимости от движений мыши вызывающего абонента или что-то в этом роде? - person MikeRand; 29.07.2010
comment
Нет. Это означает следующее: ни один опытный программист не ожидает, что подпрограмма с именем shuffle сбросит генератор случайных чисел в определенное состояние. Это просто не входит в слово shuffle. Единственная точка, где вы должны вызывать srand(), находится в функции main. В качестве руководства просто спросите себя: что делает эта функция? Ответ для функции shuffle будет таким: она перемешивает заданный массив и сбрасывает генератор случайных чисел. Одно это должно звучать достаточно странно. - person Roland Illig; 29.07.2010
comment
Устраните необходимость в 'tmp', используя std::swap в ‹алгоритме›: ... j = rand_int(i+1); std::swap(массив[i],массив[j]); - person KomodoDave; 07.07.2012
comment
@KomodoDave Это сэкономит вам одну единицу памяти, но за счет накладных расходов и переключения контекста, связанных с вызовом функции swap. Кроме того, похоже, что это чистый C, а не C++, так что, скорее всего, это не вариант. - person Cloud; 04.06.2014
comment
Обратите внимание: чтобы изолировать этот код от других генераторов случайных чисел, вы можете захотеть изучить использование nrand48() и предоставить один метод для установки случайного начального числа, а другой — для автоматического создания случайного начального числа из /dev/urandom или чего-то подобного. Это позволяет вам отделить перетасовку от любой другой генерации случайных чисел в программе (но будьте осторожны lcong48()). - person Jonathan Leffler; 25.06.2015