Generate M unique random numbers ranging from 1..N. Is there a fast algorithm?

Question

Erlang

Are there fast algorithms for generating such numbers so that they do not repeat?
We see the collection of numbers from the random number generator into a list, and checking each new one for uniqueness in the list.
The complexity of the order is seen: O(n^2)
Range M < N, and can be of the same order, order around 10000.
I can only use lists and stupid.

Answer 1

Generate array 1..N
Generate random number 0 < i < N
Extract element at this index from array
Repeat from N-1, ...., NM.

Answer 2

1) From me, a mathematician is like a gun from a stick.
2) Create an array of numbers from 1 to N.
3) Shuffle the array.
4) Take the first M numbers.

Answer 3

We need a function of bijective (1:1) projection of ordered numbers from 1 to N onto the same range.
The simplest example to get the idea across is mirroring the order of the bits in a number:

0 000 -> 000 0
1 001 -> 100 4
2 010 -> 010 2
3 011 -> 110 6
4 100 -> 001 1
5 101 -> 101 5
6 110 -> 011 3
7 111 -> 111 7

Now, to get another random, just take the next one in a row.
In the variant with bit operations, the range must be a power of two, if yours is different, you need a different function. If only she unambiguously put in correspondence with any integer from the original range, the only response from the other, and vice versa.
So you don’t have to store, mix, generate random ones. For "pseudo-randomness" you can vary the function. For example, do not mirror the order of the bits, but mix the bits in some other way. Each bit shuffle option creates a new "shuffled array" of all possible values.
The main thing is that it is quickly calculated and requires minimal resources.