> given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. > We reasonably ask that this be done in O(k

> given non-negative integers k and n with k <= n, generate a list of k distinct random numbers, each less than n. > We reasonably ask that this be done in O(k) time and O(1) additional space. Finally, the distribution must be uniform.) Sounds like the Knuth multiplicative hash. The Art of Computer Programming vol. 3, section 6.4, page 516.