Уникальные случайные числа в целочисленном массиве на языке программирования C

Ответ 1

Существует несколько способов решения вашей проблемы, каждый из которых имеет свои преимущества и недостатки.

Во-первых, я хотел бы отметить, что у вас уже есть несколько ответов, которые делают следующее: они генерируют случайное число, затем проверяют, как он уже использовался в массиве, и если он уже использовался, они просто сгенерируйте еще одно число, пока не найдете неиспользованный. Это наивная и, правда, правда, серьезная ошибка. Проблема заключается в циклическом пробном и ошибочном характере генерации числа ( "если уже используется, повторите попытку" ). Если числовой диапазон (например, [1..N]) близок к длине нужного массива (скажем, M), то в конце алгоритм может потратить огромное количество времени на поиск следующего числа. Если генератор случайных чисел даже немного сломан (скажем, никогда не генерирует какое-то число или это очень редко), то с N == M алгоритм гарантированно будет работать навсегда (или очень долго). Как правило, этот метод проб и ошибок является бесполезным, или, в лучшем случае, ошибочным.

Другой подход, уже представленный здесь, порождает случайную перестановку в массиве размера N. Идея случайной перестановки является многообещающей, но ее выполнение на массиве размера N (когда M < N) будет, безусловно, генерируют больше тепла, чем свет, говоря образно.

Хорошие решения этой проблемы можно найти, например, в Bentley "Programming Pearls" (и некоторые из них взяты из Кнута).

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

Алгоритм работает следующим образом: перебирает все числа от 1 до N и выбирает текущее число с вероятностью rm / rn, где rm - сколько чисел, которые нам еще нужно найти, а rn - сколько чисел нам все равно нужно проходить итерацию. Здесь возможная реализация для вашего случая

#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 */
}

assert(im == M);

После этого цикла мы получаем массив vektor, заполненный произвольно выбранными числами в порядке возрастания. Бит "по возрастанию" - это то, что нам здесь не нужно. Итак, чтобы "исправить", мы просто делаем произвольную перестановку элементов vektor, и мы закончили. Обратите внимание, что это перестановка O (M), не требующая дополнительной памяти. (Я не использую алгоритм перестановок. Здесь уже было показано множество ссылок.).

Если вы внимательно посмотрите на предлагаемые здесь алгоритмы на основе перестановок, которые работают с массивом длины N, вы увидите, что большинство из них в значительной степени похожи на тот же самый алгоритм Кнута, но переформулированы для M == N. В этом случае указанный выше цикл выбора будет выбирать каждое число в диапазоне [1..N] с вероятностью 1, эффективно превращаясь в инициализацию N-массива с числами от 1 до N. Принимая это во внимание, я думаю, что это скорее очевидно, что выполнение этого алгоритма для M == N, а затем обрезание результата (возможно, отбрасывание большей части его) имеет гораздо меньший смысл, чем просто запуск этого алгоритма в его первоначальном виде для исходного значения M и получение результата сразу, без какого-либо усечения.

• Алгоритм Флойда (см. здесь). Этот подход имеет сложность относительно O (M) (зависит от используемой структуры поиска), поэтому он лучше подходит, когда M < N. Этот подход отслеживает уже сгенерированные случайные числа, поэтому для этого требуется дополнительная память. Однако красота заключается в том, что он не делает ни одной из этих мерзких итераций проб и ошибок, пытаясь найти неиспользуемое случайное число. Этот алгоритм гарантированно генерирует одно уникальное случайное число после каждого вызова генератора случайных чисел.

Здесь возможная реализация для вашего случая. (Существуют разные способы отслеживания уже используемых номеров. Я просто использую массив флагов, предполагая, что N не является чрезмерно большим)

#define M 10
#define N 100    

unsigned char is_used[N] = { 0 }; /* flags */
int in, im;

im = 0;

for (in = N - M; in < N && im < M; ++in) {
  int r = rand() % (in + 1); /* generate a random number 'r' */

  if (is_used[r])
    /* we already have 'r' */
    r = in; /* use 'in' instead of the generated number */

  assert(!is_used[r]);
  vektor[im++] = r + 1; /* +1 since your range begins from 1 */
  is_used[r] = 1;
}

assert(im == M);

Почему вышеуказанные работы не сразу очевидны. Но это работает. Точно M-номера из диапазона [1..N] будут выбраны с равномерным распределением.

Обратите внимание, что для большого N вы можете использовать структуру, основанную на поиске, для хранения "уже использованных" чисел, получая при этом хороший алгоритм O (M log M) с потребностью памяти O (M).

(Хотя в этом алгоритме есть одна вещь: в то время как результирующий массив не будет упорядочен, в результате все равно будет присутствовать определенное "влияние" исходного заказа 1..N. Например, очевидно, что число N, если выбрано, может быть только самым последним членом результирующего массива. Если это "загрязнение" результата непреднамеренным упорядочением неприемлемо, результирующий массив vektor может быть случайным образом перетасован, как и в Khuth алгоритм).

Обратите внимание на самую критическую точку, наблюдаемую при проектировании этих двух алгоритмов: они никогда не зацикливаются, пытаясь найти новое неиспользованное случайное число. Любой алгоритм, который делает итерации проб и ошибок со случайными числами, является ошибочным с практической точки зрения. Кроме того, потребление памяти этими алгоритмами привязано к M, а не к N

В OP я бы рекомендовал алгоритм Флойда, поскольку в его приложении M кажется значительно меньшим, чем N, и что ему не требуется (или нет) дополнительный проход для перестановки. Однако при таких малых значениях N различие может быть незначительным.

Ответ 2

В вашем примере (выберите 10 уникальных случайных чисел от 1 до 100), вы можете создать список с номерами от 1 до 100, использовать генератор случайных чисел для перетасовки списка, а затем взять первые 10 значений из списка.

int list[100], vektor[10];
for (i = 0; i < 100; i++) {
    list[i] = i;
}
for (i = 0; i < 100; i++) {
    int j = i + rand() % (100 - i);
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;
}
for (i = 0; i < 10; i++) {
    vektor[i] = list[i];
}

Основываясь на комментариях cobbal ниже, еще лучше сказать:

for (i = 0; i < 10; i++) {
    int j = i + rand() % (100 - i);
    int temp = list[i];
    list[i] = list[j];
    list[j] = temp;

    vektor[i] = list[i];
}

Теперь O (N) устанавливает список, но O (M) выбирает случайные элементы.

Ответ 3

Я думаю, что это будет делать (я не пытался его построить, поэтому синтаксические ошибки оставляют для исправления как упражнение для читателя). Там могут быть более элегантные способы, но это решение грубой силы:

int vektor[10];    
int random;
int uniqueflag;
int i, j

for(i = 0; i < 10; i++) {
     do {
        /* Assume things are unique... we'll reset this flag if not. */
        uniqueflag = 1;
        random = rand() % 100+ 1;
        /* This loop checks for uniqueness */
        for (j = 0; j < i && uniqueflag == 1; j++) {
           if (vektor[j] == random) {
              uniqueflag = 0;
           }
        }
     } while (uniqueflag != 1);
     vektor[i] = random;
}

Ответ 4

Простое генерирование случайных чисел и наблюдение, насколько они в порядке, - это плохой способ решить эту проблему в целом. Этот подход принимает все возможные значения, перетасовывает их, а затем занимает первую десятку. Это прямо аналогично перетасовке колоды карт и удалению сверху.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define randrange(N) rand() / (RAND_MAX/(N) + 1)

#define MAX 100        /* Values will be in the range (1 .. MAX) */
static int vektor[10];
int candidates[MAX];

int main (void) {
  int i;

  srand(time(NULL));   /* Seed the random number generator. */

  for (i=0; i<MAX; i++)
    candidates[i] = i;

  for (i = 0; i < MAX-1; i++) {
    int c = randrange(MAX-i);
    int t = candidates[i];
    candidates[i] = candidates[i+c];
    candidates[i+c] = t;
  }

  for (i=0; i<10; i++)
    vektor[i] = candidates[i] + 1;

  for (i=0; i<10; i++)
    printf("%i\n", vektor[i]);

  return 0;
}

Для получения дополнительной информации см. comp.lang.c FAQ вопрос 13.19 для перетасовки и вопрос 13.16 о генерации случайных чисел.

Ответ 5

Один из способов - проверить, содержит ли массив уже новое случайное число, и если да, сделайте новый и повторите попытку.

Это открывает возможность (random;)), что вы никогда не получите число, которое не находится в массиве. Поэтому вы должны подсчитать, сколько раз вы проверяете, уже ли номер в массиве, и если счетчик превышает MAX_DUPLICATE_COUNT, выбросьте исключение или так:) (EDIT, увидев, что вы находитесь на C. Забудьте об исключительной части:) Верните ошибку вместо этого: P)

Ответ 6

Быстрое решение - создать массив масок всех возможных чисел, инициализированных нулями, и установить запись, если это число сгенерировано

int rand_array[100] = {0};
int vektor[10];   
int i=0, rnd;
while(i<10) {
    rnd = rand() % 100+ 1;
    if ( rand_array[rnd-1] == 0 ) {
        vektor[i++] = rnd;
        rand_array[rnd-1] = 1;
    }
}

Ответ 7

Создайте первую и вторую цифры отдельно. Перетасуйте их позже, если потребуется. (синтаксис из памяти)

int vektor[10];
int i = 0;

while(i < 10) {
  int j = rand() % 10;
  if (vektor[j] == 0) { vektor[j] = rand() % 10 + j * 10; i ++;}
}

Однако числа будут почти разнесены на n, 0 < n < 10.

Кроме того, вам нужно сохранить отсортированные числа (O(n log n)), чтобы вновь сгенерированные могли быстро проверяться на наличие (O(log n)).

Ответ 8

Ниже приведен метод среднего времени O (M).

Метод: если M <= N/2, используйте процедуру S (M, N) (ниже) для создания массива результатов R и возвращайте R. Если M > N/2, используйте процедуру S (NM, N) для генерации R, затем вычислить X = {1..M}\R [дополнение R в {1..M}], перетасовать X с Fisher-Yates shuffle [во времени O (M)] и вернуть X.

В случае M > N/2, где O (M) == O (N), существует несколько быстрых способов вычисления дополнения. В приведенном ниже коде для краткости я включил только пример процедуры S (M, N), закодированный inline в main(). Перемешивание Фишера-Йейта - O (M) и проиллюстрировано главным ответом на соответствующий вопрос # 196017. Другие предыдущие связанные вопросы: # 158716 и # 54059.

Причина того, что S (M, N) принимает время O (M) вместо O (N) времени, когда M < N/2 состоит в том, что, как описано в проблема купонов-собирателей, ожидание E (t_k) является kH_k, из которого E (t_ {k/2}) = k (H_k - H_ {k/2}) или около k * (ln (k) -ln (k/2) + O (1)) = k * (ln (k/(k/2) ) + O (1)) = k * (ln (2) + O (1)) = O (k).

Процедура S (k, N): [Тело этой процедуры представляет собой дюжину строк после комментария "Gen M различных случайных чисел" в приведенном ниже коде.] Выделите и инициализируйте три целых массива M + 1 элементов H, L и V ко всем значениям -1. Для я = 0 - M-1: Поместите случайное значение v в V [i] и в часовое node V [-1]. Получите одну из M списков из H [v% M] и следуйте за этим списком, пока не найдете совпадение с v. Если совпадение находится в V [-1], v - новое значение; поэтому заголовок списка обновлений H [v% M] и список ссылок L [i]. Если совпадение не находится на V [-1], получите и проверьте другой v и т.д.

Каждый шаг "следовать за списком" ожидал стоимость O (1), потому что на каждом шаге, кроме последней, средняя длина списка меньше 1. (В конце обработки списки M содержат M элементов, поэтому средняя длина постепенно возрастает до 1).

 // randomMofN - jiw 8 Nov 2011     
 // Re: https://stackoverflow.com/questions/1608181/
 #include <stdlib.h>
 #include <stdio.h>
 int main(int argc, char *argv[]) {
   int h, i, j, tM, M, N, par=0, *H, *L, *V, cxc=0;
   // Get M and N values
   ++par; M = 42;  if (argc > par) M = atoi(argv[par]);
   ++par; N = 137; if (argc > par) N = atoi(argv[par]);
   tM = 3*M+3;
   H = malloc(tM*sizeof(int));
   printf ("M = %d,  N = %d  %s\n", M, N, H?"":"\nmem error");
   if (!H) exit(13);
   for (i=0; i<tM; ++i)           // Init arrays to -1's
     H[i] = -1;
   L = H+M;  V = L+M;

   // Gen M distinct random numbers
   for (i=0; i<M; ++i) {
     do {
       ++cxc;                     // complexity counter
       V[-1] = V[i] = random()%N;
       h = V[i]%M;                // h = list-head index
       j = H[h];
       while (V[j] != V[i])
         j = L[j];
     } while (j>=0);
     L[i] = H[h];
     H[h] = i;
   }

   // Print results
   for (j=i=0; i<M; ++i) {
     j += printf ("%4d ", V[i]);
     if (j>66) j = printf ("\n");
   }
   printf ("\ncxc %d\n", cxc);
   return 0;
 }

Ответ 9

Мне нравится алгоритм Флойда.

но мы можем взять все случайные числа от 0 до M (не до in):

#define M 10
#define N 100    

unsigned char is_used[N] = { 0 }; /* flags */
int in, im;

im = 0;

for (in = N - M; in < N && im < M; ++in) {
  int r = rand() % (N + 1); /* generate a random number 'r' */

  while (is_used[r])
  {
     /* we already have 'r' */
     r = rand() % (N + 1);
  }
  vektor[im++] = r + 1; /* +1 since your range begins from 1 */
  is_used[r] = 1;
}

assert(im == M);