5

Como posso gerar uma grande sequência de números aleatórios que não se repetem?

Tenho que gerar 10 000 mil números de 1 ate 1 milhão e guardar em um arquivo e eles não podem se repetir. Por mais que a sequência seja grande, tem alguns números que se repetem.

#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;
}
1
  • A resposta resolveu o seu problema? Acha que pode aceitá-la agora? Veja o tour para entender como funciona. Ajudaria muito indicar para todo mundo que a solução foi útil e satisfatória para você. Também pode votar em qualquer pergunta ou resposta que achar útil no site todo.
    – Maniero
    Commented 17/09/2016 às 17:04

4 Respostas 4

9

A solução mais simples e universalmente aceita é usar o algoritmo Fisher-Yates que consiste em armazenar todos os números possíveis, portanto você tem o controle de que eles não se repetirão, e só depois embaralhar aleatoriamente estes números, pegando depois os primeiros números já devidamente embaralhados.

Solução simples, completa sem dependências:

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

Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.

Acredito que essa forma é suficiente, para gerar uma sequência não tendenciosa complicaria um pouco mais, em geral o pessoal trabalha dessa forma em coisas simples. Se quiser insistir poderia criar uma função para gerar os números aleatórios, o que consumiria bem mais tempo, algo assim:

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

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

Mas pra falar a verdade não sei se para esse volume de números que podem ser sorteados e a desproporção que serão usados, compensa fazer esse tipo de algoritmo. Vai depender da necessidade e disponibilidade de recursos.

Acredito que guardar em arquivo não seja o problema da questão, não coloquei nada.

1
  • 1
    Atenção aos indices: numero[0] não foi atribuido; numero[MAX - 1] pode causar "index out of bounds"; a função shuffle() sofre de bias.
    – pmg
    Commented 21/06/2016 às 12:18
3

Você deve registrar os números que já saíram e gerar outro caso saia ele. Para isso, é bom armazenar os números em uma lista. Código disponível Aqui.

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

Assim, o sistema só encerará quando gerar todos os números, sendo todos diferentes.

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

Uma maneira eficiente de gerar números aleatórios sem repetição é guardar os números todos num array, baralhar esse array, e seguidamente seleccionar a quantidade de números pretendidos.

#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]);

Para a função shuffle() é normalmente usado o método de Knuth.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .