2
$\begingroup$

Is there an efficient method of sampling an n-choose-k combination at random (with uniform probability, for example)?

I have read this question but it asks for generations of all combinations, not combinations at random.

I general I'm aware of rejection sampling, however it's very inefficient.

I also came across reservoir sampling, but that appears to be primarily geared towards very large or unknown n. I'm more interested in large but finite n (definitely not large enough to not be able to fit in memory. Well. An n-sized array itself will fit in memory, but the state space of all n-choose-k combinations might not).

Is there any survey/review on this topic? Does Knuth cover random n-choose-k sampling in his TAOCP texts?

Thanks in advance.

Edit: To be a bit more specific, a 5-choose-3 space over the string 'ABCDE' would look like this:

['ABC', 'ABD', 'ABE', 'ACD', 'ACE', 'ADE', 'BCD', 'BCE', 'BDE', 'CDE']

(Note: this is combination without replacement). And I want to be able to sample from this space with uniform distribution, using a general algorithm (one that works with arbitrary n and k).

$\endgroup$
  • $\begingroup$ oeis.org/wiki/Ranking_and_unranking_functions $\endgroup$ – D.W. Feb 27 at 19:40
  • $\begingroup$ @D.W. the ranking function is a nice approach. If "the state space of all n-choose-k combinations might not" fit in the memory, however, it might not be an immediate hit. $\endgroup$ – Apass.Jack Feb 27 at 20:01
  • 2
    $\begingroup$ Reservoir sampling solves exactly this problem in $O(n)$ time. Can you elaborate why it won't work for you? $\endgroup$ – orlp Feb 27 at 20:28
  • $\begingroup$ @Apass.Jack, for what it's worth, ranking/unranking functions don't require storing the set of all such combinations (just an index into that set). In any case, orlp has a reasonable answer, so it's moot here. $\endgroup$ – D.W. Feb 27 at 20:56
  • $\begingroup$ @D.W. I meant the index might be out of the memory. For example, if $n=1000000$ and $k=100000$. $\endgroup$ – Apass.Jack Feb 27 at 21:13
2
$\begingroup$

Reservoir sampling solves exactly this problem in $O(n)$ time. When $n$ is really large, but you can calculate the $i$th element just from the index $i$ in $O(1)$ time then you can simulate the sampling by getting the first $k$ elements from a random permutation of $\{1, \dots, n\}$ in $O(k \log n)$ time using Sometimes-Recurse Shuffle.

$\endgroup$
2
$\begingroup$

Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively.


Input: two positive integers $n$ and $k$ with $k\le n$
Output: a random permutation of $k$ integers from $1,2,\cdots,n$
Algorithm:

  1. Let arr be an array of size $n$ and a default value that is not True.
  2. Let out be an empty array.
  3. Let i be a random integer in $[0,n)$. If arr[i] is not True, append i+1 to out and set arr[i] to True.
  4. Go back to 3 unless we have selected $k$ elements.
  5. return out.

If $k\le n/2$, then the algorithm above runs in $O(k)$ average time. For example, if $n=1000$ and $k=50$, it will use the random number generator less than 55 times in average. This is much better the reservoir sampling that will use the random number generator about 1000 times.


How to speed up the algorithm if $k$ is not much smaller than $n$?

We will let each element in arr be a pair (i, False). After we have selected $n/4$ elemented, we will compactify arr by removing the elements whose second entries have been changed to True. We will set $n$ to $n-n/4$ and $k$ to $k-n/4$. Repeat the algorithm.

$\endgroup$
  • $\begingroup$ The speed-up can be tuned in various ways. If somebody have found a reference along this approach, please edit my answer. $\endgroup$ – Apass.Jack Feb 27 at 21:19
  • $\begingroup$ if $k\ge n/2$, we can run the algorithm with $k$ replaced by $n-k$ and return the elements that are not selected. $\endgroup$ – Apass.Jack Feb 27 at 21:23

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.