Генерация массива уникальных случайных чисел - PullRequest
Новая
       7

Генерация массива уникальных случайных чисел

4 голосов
/ 12 марта 2019

Я пишу функцию, которая должна заполнять массив случайными числами от 0 до n (где n передается аргумент функции), но все числа в массиве должны быть уникальными. Мне в основном нужно перетасовать массив чисел от 0 до n

Я нашел этот ответ здесь: Уникальные случайные числа в массиве целых чисел на языке программирования C

И использовал «алгоритм Кнута», предложенный пользователем: 

void generate_random_array(int count)
{
  int in, im;

  im = 0;
  srand(time(NULL));

  for (in = 0; in < count && im < count; ++in) {
    int rn = count - in;
    int rm = count - im;
    if (rand() % rn < rm) random_array[im++] = in; 
  }
}

Однако эта функция вообще не генерирует для меня случайные числа, она просто создает массив чисел от 0 до количества. Как я могу сгенерировать фактическую случайную последовательность уникальных чисел.

Ответы [ 2 ]

8 голосов
/ 12 марта 2019

Пример реализации алгоритма C в приведенном вами ответе следующий: 

#define M 10
#define N 100

int in, im;

im = 0;

for (in = 0; in < N && im < M; ++in) {
  int rn = N - in;
  int rm = M - im;
  if (rand() % rn < rm)    
    /* Take it */
    vektor[im++] = in + 1; /* +1 since your range begins from 1 */
}

Алгоритм Кнута. Это очень простой алгоритм со сложностью O (N) (то есть числового диапазона), , что означает, что он наиболее пригоден для использования, когда M близок к N.

но вы устанавливаете M == N, что не близко, но равно

Итак, начальные значения rn и rm одинаковы. поэтому, который не может заставить алгоритм работать должным образом, потому что: 

whatever % rn < rm

всегда верно, как 345436 % 22 < 22, так как a % b < b, всегда.

Таким образом, проверка всегда выполняется, целое число сохраняется каждый раз, поэтому in и im увеличиваются на 1 каждый раз и т. Д.

Мне нужно перетасовать массив чисел от 0 до n

Этот алгоритм не тот, который вам нужен: он вообще не тасует массив, он выдает упорядоченные случайные числа (а значит, уникальные), выбирая одно из возрастающих значений время от времени. Ограничение значений, как вы делаете, заставляет алгоритм выдавать все значения диапазона.

Вам повезет больше с Перемешивающим массивом в C

1 голос
/ 12 марта 2019

Мне нужно перетасовать массив чисел от 0 до n

Ну тогда почему бы не сделать это ? Алгоритм Кнута предназначен для выбора случайного подмножества из всего указанного диапазона, который он выбрасывает в порядке возрастания. Это , которое подмножество является случайным, а не порядок элементов, но есть только одно подмножество, которое содержит всех элементов. В любом случае, если вы хотите, чтобы они были в случайном порядке, вам все равно нужно перетасовать результат алгоритма Кнута, который оставляет вас именно там, где вы начали.

...