# Generate a random combination in O(k) time and space?

How to generate a random combination of $$k$$ numbers from $$n$$ choices in $$O(k)$$ time and space, if we can generate a random number between 1 and $$O(n)$$ in $$O(1)$$ time?

I know only 3 algorithms: with $$O(n)$$ time and space, $$O(k\log k)$$ time and $$O(k)$$ space, $$O(k)$$ average time and $$O(n)$$ space. Is it even possible to solve this task on $$O(k)$$ both?

• Are you allowed to use hashing? – Yuval Filmus Feb 24 '19 at 17:20
• @yuval-filmus no – Gleb Feb 24 '19 at 17:26
• Perhaps you can implement it using the randomness you're allowed to generate. Even pairwise independent hashing might suffice. – Yuval Filmus Feb 24 '19 at 17:27

Suppose that $$k \leq n/2$$ (the constant $$1/2$$ is arbitrary) – otherwise you can just use the $$O(k)$$ time, $$O(n)$$ space algorithm, which is the second algorithm that you mention.

One way of solving your problem is as follows:

• Repeat $$k$$ times:
1. Generate a random number from $$1$$ to $$n$$.
The expected number of steps in this algorithm is $$\frac{1}{1-0/n} + \frac{1}{1-1/n} + \cdots + \frac{1}{1-k/n} = n \left(\frac{1}{n} + \cdots + \frac{1}{n-k}\right) \leq \frac{k}{2},$$ since $$k \leq n/2$$.
Using a hash table, use should be able to implement step 2 in $$O(1)$$ expected time and $$O(k)$$ space.