How do I generate random numbers and without repeating them in a time interval?

4

I'm creating a 'game' in which the user needs to choose a range, and in this interval, he chooses how many random numbers he wants to generate. However, in random numbers generated, there can be no repetitions, for example:
Range 1 to 10, show 10 random numbers in this range.
There can not be two numbers 8 etc, but I do not know how to put them to repeat them. Here is the code:

printf("GERADOR DE N NÚMEROS ALEATÓRIOS\n");
printf("Digite o número máximo do intervalo: ");
scanf("%d", &intervalo); //Lê o intervalo máximo proposto pelo usuário.

printf("Intervalo proposto: [1 a %d]\n\n", intervalo); //Mostra na tela o intervalo proposto pelo usuário.

printf("Digite quantos números aleatórios e diferentes deseja gerar: ");
srand(time(NULL)); //Complementa o comando rand. Toda vez que executar o programa, os números gerados não estejam na mesma sequência que anteriormente.
scanf("%d", &n); //Lê a quantidade de números que serão mostrados na tela

for(i=1; i<=n; i++) // Coemça o intervalo em i, e mostra a quantidade de números até chegar em "n" que representa o intervalo proposto pelo usuário.
    printf("%dº número: %d\n",i, 1+(rand()%intervalo)); //Aqui é onde é imprimido na tela o número aleatório gerado, entretanto, ele precisa ser diferente do número anterior gerado.

system("PAUSE");
return 0;

}

    
asked by anonymous 29.11.2015 / 19:38

2 answers

4

One way to do this is to use array , std:set or std::unordered_set (C ++ 11 or higher) to store intermediate values. sets are especially interesting since they do not allow repetitions:

std::unordered_set<int> numbers;
for(int i=1; i<=n; i++) { 
    int number = 1 + (rand() % intervalo);
    bool inseriu = numbers.insert(number).second;
    if (inseriu) {
        printf("%dº número: %d\n",i, number); 
    } else {
        printf("\t*%d é um número repetido, tentando novamente\n", number);
        i--;
    }
}

See that unordered_set::insert returns pair<iterator,bool> . The iterator points to the newly inserted element (or the element with the same value), while the bool indicates whether the element has been entered or not.

The difference between set and unordered_set is that the first one uses an ordered tree (eg, Red-black tree ) with insertion time / search O(log(n)) . The second uses a dispersion table , sacrificing the order for deprecated insertion times O(1) . In your case unordered_set seems to make more sense.

If the range is small enough, a workaround is to construct a vector containing the entire range, shuffle and choose the% of first% elements.

std::vector<int> numbers2(intervalo);
std::iota(numbers2.begin(), numbers2.end(), 1);
std::random_shuffle(numbers2.begin(), numbers2.end());
for (int i=0; i<n; i++) {
    printf("%dº número: %d\n",i+1, numbers2[i]);    
}

In this example the function n initializes the iota with the range numbers and the function vector shuffles these values. This algorithm is interesting, for example, to simulate a player shuffling cards.

Functional example in Ideone

    
29.11.2015 / 20:50
2

In C, the usual way to solve the problem of randomness without repetition is to put all possible values into an array, shuffle the array, and choose the first% of elements%.

int limite_inferior, limite_superior, quantidade;
// obter valores, eg
limite_inferior = 1;
limite_superior = 100;
quantidade = 30;

if (limite_superior < limite_inferior) /* erro */;
int alcance = limite_superior - limite_inferior + 1;
if (quantidade > alcance) /* erro */;

int *array = malloc(alcance * sizeof *array);
for (int k = 0; k < alcance; k++) array[k] = k + limite_inferior;

shuffle(array, alcance);
for (int k = 0; k < alcance; k++) printf("%d ", array[k]);

For the N function, see, for example, the Wikipedia article on Knuth Shuffle .

    
30.11.2015 / 15:16