Generating unique random numbers in C

Question

I tried generating 10 unique random numbers in C. I have an array numout[] for 10 numbers but this gets to "segmentation fault" after some time.

Tho code is:

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);
}

We can't see how you declare `numout`. This code doesn't even compile. In what sense would these numbers be unique? — David Heffernan, Feb 21 '11 at 09:46
Where's the declaration of numout[], what's "i" and "mul_val"? — Erik, Feb 21 '11 at 09:47
-1 ... and what is `i`, can't tell what's wrong because code is incomplete — Binary Worrier, Feb 21 '11 at 09:48

score 12 · Accepted Answer · edited May 23 '17 at 12:18

Throw that code away, seriously. You need a shuffling algorithm, not a piece of code that checks older values for duplicates. Doing it your way will end up taking longer and longer as your pool runs out. The advantage of a shuffling algorithm is that it doesn't degrade as the pool becomes smaller.

Here's a piece of code I used in answering a different question. It maintains a list of numbers and, when it returns a random one to you, it removes it from the list and decrements the count for the next random selection.

#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;
}

A sample output shows it in action:

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

Call it with a non-negative pool size and it sets up a new sequence and returns the first random value. Following that, you can call it with -1 and it will get the next random, unique number from the pool. When the pool is exhausted, it will return -1.

The other answer that contained this code has a version that can maintain multiple pools as well if you want to be able to use this function in threaded code.

score 3 · Answer 2 · answered Feb 21 '11 at 09:56

You will get a segmentation fault when you run out of stack space. Your code is recursive (i.e. generate() calls generate()). So when you run out of unused random numbers, it will call itself forever.

However, I will not recommend a fix for your code, because you really need to write it again from scratch. Follow paxdiablo's example.

score 2 · Answer 3 · answered Feb 15 '17 at 23:51

If you need a large set of unique random numbers you should consider using LFSR approach. LFSR generates unique random numbers that does not repeat unless the entire pool is exhausted, so a 32-bit LFSR will generate 2^32 - 1 unique random numbers -- It does not generate 0. The coding is straight forward, look it up in google.

Swaroop · Answer 4 · 2013-02-18T19:36:04.163

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();
}

Generating unique random numbers in C

4 Answers4

Linked

Related