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

Question

I am creating a 'game' in which it is necessary for the user to choose an interval, and in this interval, he chooses how many random numbers he wants to generate. However, in the random numbers generated, there can be no repetitions, for example:
Range 1 to 10, show 10 random numbers in this range.
There can be two numbers 8 etc, but I do not know how to put not to repeat them. Follow 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 1

One way to do this is to use a array, std:set or std::unordered_set (C++11 or higher) to store intermediate values. The 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 a pair<iterator,bool>. The iterator points to the newly inserted element (or the element with the same value), while the bool indicated whether the item has been inserted or not.

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

---

If the range is small enough, an alternative solution is to build a vector containing the entire range, shuffle and choose the n 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 iota initializes the vector with the interval numbers and the function random_shuffle shuffles these values. This algorithm is interesting, for example, to simulate a player shuffling cards.

Functional example in Ideone

Answer 2

In C, the usual way to solve the randomness problem without repetition is to put all possible values in an array, shuffle the array and choose the first ones N 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 function shuffle() see, for example, the Wikipedia article on Knuth Shuffle.