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

Question

Я попытался сгенерировать 10 уникальных случайных чисел в C. У меня есть массив numout[] для 10 чисел, но через некоторое время это приводит к "ошибке сегментации".

код:

int i,j,numout[10],randnum;

void main()
{
    srand(time(NULL));  
    for(i=0;i<10;i++)
    {
        numout[i]=generate();
        printf("%d",numout[i]);
        fflush(stdout);
        sleep(1);
        printf("\b");
    }
}
int generate()
{
    randnum=1+(int)(rand()*mul_val/(RAND_MAX+1.0));
    for(j=0;j<i;j++)
    {
        if(randnum==0 || randnum==numout[j])
        {
            randnum=generate();     
        }
    }
    return(randnum);
}

Answer 1

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

Вот фрагмент кода, который я использовал при ответе на другой вопрос. Он поддерживает список чисел и, когда возвращает вам случайное число, удаляет его из списка и уменьшает счетчик для следующего случайного выбора.

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

#define ERR_NO_NUM -1
#define ERR_NO_MEM -2

int myRandom (int size) {
    int i, n;
    static int numNums = 0;
    static int *numArr = NULL;

    // Initialize with a specific size.

    if (size >= 0) {
        if (numArr != NULL)
            free (numArr);
        if ((numArr = malloc (sizeof(int) * size)) == NULL)
            return ERR_NO_MEM;
        for (i = 0; i  < size; i++)
            numArr[i] = i;
        numNums = size;
    }

    // Error if no numbers left in pool.

    if (numNums == 0)
       return ERR_NO_NUM;

    // Get random number from pool and remove it (rnd in this
    //   case returns a number between 0 and numNums-1 inclusive).

    n = rand() % numNums;
    i = numArr[n];
    numArr[n] = numArr[numNums-1];
    numNums--;
    if (numNums == 0) {
        free (numArr);
        numArr = 0;
    }

    return i;
}

int main (void) {
    int i;

    srand (time (NULL));
    i = myRandom (20);
    while (i >= 0) {
        printf ("Number = %3d\n", i);
        i = myRandom (-1);
    }
    printf ("Final  = %3d\n", i);
    return 0;
}

Пример вывода показывает это в действии:

Number =  19
Number =  10
Number =   2
Number =  15
Number =   0
Number =   6
Number =   1
Number =   3
Number =  17
Number =  14
Number =  12
Number =  18
Number =   4
Number =   9
Number =   7
Number =   8
Number =  16
Number =   5
Number =  11
Number =  13
Final  =  -1

Называйте его с неотрицательным размером пула, и он устанавливает новую последовательность и возвращает первое случайное значение. После этого вы можете позвонить по номеру -1, и он получит следующий случайный уникальный номер из пула. Когда пул исчерпан, он вернет -1.

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

Answer 2

Вы получите ошибку сегментации, когда исчерпаете пространство стека.Ваш код рекурсивен (т.е. generate() вызывает generate()).Поэтому, когда у вас заканчиваются неиспользуемые случайные числа, он будет называть себя вечно.

Однако я не буду рекомендовать исправление для вашего кода, потому что вам действительно нужно написать его заново с нуля.Следуйте примеру Паксиабло.

Answer 3

Если вам нужен большой набор уникальных случайных чисел, вы должны рассмотреть возможность использования подхода LFSR.LFSR генерирует уникальные случайные числа, которые не повторяются, если не исчерпан весь пул, поэтому 32-битный LFSR сгенерирует 2 ^ 32 - 1 уникальное случайное число - он не генерирует 0. Кодировка прямолинейна, посмотрите вGoogle.

Answer 4

The program below stores n unique random numbers i.e, from [1 to n] in an array.

#include<iostream.h>
#include<conio.h>

void main()
{

int i, j, Array[100];
cout<<"Enter value of n : ";     //upper limit
cin>>n;

randomize();

int rnd;

Array[1]=rand()%n+1;

for(i=2;i<=n;i++)
{
    rnd=rand()%n+1;

     for(j=1;j<i;j++)
     {
        if(rnd==Array[j])
        {
            i--;
            break;
        }
    }

        if(j>=i)
        Array[i]=rnd;
}



//for printing from random numbers from 1 to n
for(i=1;i<=n;i++)
cout<<Array[i]<<"\n";

getch();
}