performance - Unique random number algorithm -

i algorithm/function that, given number n, generates random numbers 0 n - 1 in constant time. after nth call, function may pleases. also, important algorithm generates numbers when requested rather using shuffling, because may (and in average case do) not need full list of numbers. best approach take?

(optional read) thought of having hash set of numbers, , pulling numbers out 1 @ time, require inserting elements (which not need) hash set first... not work... argh

thanks in advance.

modify fisher–yates shuffle replacing array map stores elements have been moved. in python:

import random class shuffle:     def __init__(self, n):         self.d = {}         self.n = n     def generate(self):         = random.randrange(self.n)         self.n -= 1         di = self.d[i] if in self.d else  # idiomatically, self.d.get(i, i)         dn = self.d[self.n] if self.n in self.d else self.n         self.d[i] = dn         self.d[self.n] = di         return di 

the space usage , amortized expected running time o(1) words per element generated. log factors, optimal.