Question:
I'm creating a 'game' in which the user is required to choose a range, and in this range, he chooses how many random numbers he wants to generate. However, in the generated random numbers, there can be no repetitions, for example:
Range 1 to 10, show 10 random numbers in this range.
There can't be two numbers 8's etc, but I don't know how to put them so I don't repeat them. Here's 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;
}
Answer:
One way to do this is to use an array , std:set or std::unordered_set (C++11 or higher) to store the intermediate values. Sets are especially interesting since they don't 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 a 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 inserted or not.
The difference between set and unordered_set is that the former uses an ordered tree (eg, Red-Black Tree ) with O(log(n)) insert/fetch time. The second uses a hash table , sacrificing order for O(1) amortized insertion times. In your case unordered_set seems to make more sense.
If the range is small enough, an alternative solution is to construct a vector containing the entire range, shuffle and choose the first n 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 iota function initializes the vector with the range numbers and the random_shuffle function shuffles these values. This algorithm is interesting, for example, to simulate a player shuffling cards.