Generate random numbers that do not repeat

Question

How can I generate a large sequence of random numbers that do not repeat?

I have to generate 10,000 numbers from 1 to 1 million and store them in a file and they can’t repeat themselves. However large the sequence is, it has some repeating numbers.

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

int main(){
int i;
FILE *fp;
fp = fopen("aleatorios.txt", "w");
if(fp == NULL){
    printf("erro.\n");
    return 1;
}
srand( (unsigned) time(NULL));
for(i=1; i<10000; i++){
    fprintf(fp, "%d\n", 1 + rand()% 999999);
}
fclose(fp);
return 0;
}

Answer 1

The simplest and universally accepted solution is to use the algorithm Fisher-Yates which consists of storing all possible numbers, so you have control that they will not repeat themselves, and only then randomly shuffle these numbers, picking up the first numbers already properly shuffled.

Simple, complete solution without dependencies:

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

#define MIN 1
#define MAX 1000000
#define QTDE 10000  //precisa ser menor que MAX

void shuffle(int *array) {
    for (int i = MAX - MIN - 1; i > 0; i--) {
        int j = rand() % (i + 1);
        int tmp = array[j];
        array[j] = array[i];
        array[i] = tmp;
    }
}

int main(void) {
    srand(time(NULL));
    int * numeros = malloc((MAX - MIN) * sizeof(int));
    if (!numeros) exit(EXIT_FAILURE);
    for (int i = 0; i < MAX - MIN; i++) {
        numeros[i] = i + MIN;
    }
    shuffle(numeros);
    for (int i = 0; i < QTDE; i++) {
        printf("%d\n", numeros[i]);
    }
    return 0;
}

Behold working in the ideone. And in the repl it.. Also put on the Github for future reference.

I believe that this form is sufficient, to generate a sequence not biased would complicate a little more, in general the staff works this way in simple things. If you want to insist you could create a function to generate the random numbers, which would take a lot more time, something like that:

int rand_int(int n) {
    int limit = RAND_MAX - RAND_MAX % n;
    int rnd;

    do {
        rnd = rand();
    } while (rnd >= limit);
    return rnd % n;
}

But to tell you the truth I don’t know if for this volume of numbers that can be drawn and the disproportion that will be used, it pays to do this type of algorithm. Will depend on the need and availability of resources.

I believe that storing in file is not the problem, I did not put anything.

Answer 2

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

#define NUMS_NEEDED 10000

int main()
{
    int sizeArray = 0;
    int i = 0, j = 0;
    int nums[NUMS_NEEDED];
    FILE *fp = NULL;

    srand( time( NULL ) );
    fp = fopen( "aleatorios.txt", "w" );

    if( fp == NULL )
    {
        printf( "erro.\n" );
        return 1;
    }
    while( sizeArray < NUMS_NEEDED )
    {
        int numGenerated = 1 + rand()% 999999;
        // Verifica se o número já existe
        for( i = 0 ; i < sizeArray ; ++i )
        {
            if( nums[i] == numGenerated )
            {
                break;
            }
        }
        if( i == sizeArray )
        {
            fprintf( fp, "%d\n", numGenerated );
            nums[++sizeArray] = numGenerated;
        }
    }

    fclose( fp );
    fp = NULL;
    return 0;
}

Answer 3

You should register the numbers that have already left and generate another case out it. For this, it is good to store the numbers in a list. Available code Here.

int n;
Stack *list = NULL;
Stack *buff = NULL;
for(i=1; i<10000; i++){
    n = rand() % 999999;

    buff = list;
    while(buff){ // percorre a lista
        if(buff->data == n){
            i--; // ignora um loop;
            continue;
        }
        buff = buff->next; // vai para o proximo item da lista;
    }

    // se não houver números repetidos, executa esse trecho do código
    stack_push(n, &list);
    fprintf(fp, "%d\n", 1 + n);
}

Thus, the system will end only when generating all the numbers, all being different.

Answer 4

An efficient way to generate random numbers without repetition is to store all numbers in an array, shuffle that array, and then select the amount of numbers desired.

#define RANGE 1000000
#define QUANT 10000

int *numeros;
numeros = malloc(RANGE * sizeof *numeros);
if (!numeros) exit(EXIT_FAILURE);
for (int k = 0; k < RANGE; k++) numeros[k] = k + 1;

shuffle(numeros, RANGE); /* é usual usar método de Knuth */

for (int k = 0; k < QUANT; k++) printf("%d\n", numeros[k]);

For the function shuffle() is usually used the knuth method.