[Solved]: Efficiently generating a uniformly random list of unique integers in a range

Problem Detail: 

The problem:

• To generate a list of size $n$,
• Containing unique integers,
• Sampled uniformly in the range $\left[0,m\right)$,
• In $O(n)$ time, except that:
  • Assuming $m$ is bounded by some word-size, $\left|m\right|$, the specific time should be $O(n\cdot\left|m\right|)$, as one cannot do better than this.

Apologies if this is a duplicate, if you find one, feel free to point it out.

---

EDIT: to clarify, the question implies that we are concerned the complixity in terms of bit-operations. (See logarithmic cost model).

Asked By : Realz Slaw

Answered By : Yuval Filmus

Here is a solution in $O(n\log n)$ (with high probability). We consider two cases: $n\log n \geq m$ and $n\log n \leq m$. In the first case, we choose a random permutation of $[0,m)$ and take only the first $n$ elements. This takes time $O(m) = O(n\log n)$. In the second case, we maintain a balanced binary search tree (or equivalent), adding to it random elements from $[0,m)$ one by one, checking for duplicates each time. In expectation we need to try at most $1/\log n = o(1)$ extra times for each element, so the expected running time of this algorithm is $O(n\log n)$. In fact, the running time is $O(n\log n)$ also with high probability.

We can obtain an expected $O(n)$ solution by replacing the balanced binary search tree with a hash table, and changing the cutoff to $n \geq m/2$ versus $n \leq m/2$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52530

3.2K people like this

 Download Related Notes/Documents