Generate random numbers from 1 to n without duplicate in O(1) space

Question

One way is to use an array of size n such that a[i]=i.

Now shuffle it.

Then use a loop to print the numbers. But can it be done without using the array?

Ps: Please do not use any inbuilt Random generator function. I am trying to get a logical answer and write that random function myself.

Answer 1

I'd say it depends on the quality of the random numbers you want to get.

An extreme case is to output the identity permutation and claim it's random. OK, they don't really look random at all.

A slightly more plausible solution is to take some prime p > n and some integer a > 1 which is a primitive root modulo p, and then look at a mod p, a^2 mod p, a^3 mod p, ..., a^{p-2} mod p. This will be a permutation of numbers 2, 3, ..., p - 1. Discard everything which is greater than n, and output the rest. (And insert the missing 1 at a random position somehow.) All this can be done in O(1) additional memory, by repeatedly doing x -> (x*a) mod p and discarding elements > n on the fly. And the result may be random enough for some applications: with a right choice of a, it will at least look pretty random to an untrained human eye. Still, not much more than that.

For obtaining quality random numbers, I doubt there is a general solution which uses O(1) additional memory. But don't take my word for it. Let's see what the other answers may bring.