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?

  • $\begingroup$ Are you allowed to use hashing? $\endgroup$ – Yuval Filmus Feb 24 '19 at 17:20
  • $\begingroup$ @yuval-filmus no $\endgroup$ – Gleb Feb 24 '19 at 17:26
  • 1
    $\begingroup$ Perhaps you can implement it using the randomness you're allowed to generate. Even pairwise independent hashing might suffice. $\endgroup$ – 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:

  • Start with the empty list.
  • Repeat $k$ times:
    1. Generate a random number from $1$ to $n$.
    2. Check if it is already in the list.
    3. If so, go back to step 1.
    4. Otherwise, add it to the list.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.