Task: Produce one of the Binomial(n,k) k-element subsets of an N-element universe uniformly at random. It's pretty easy to figure out how to do that in O(k) steps if 0<k<=n/2, e.g. j=0; i=0; LoopForever{ if( rand01()*n <= k ){ k--; A[j]=i; j++; if(k==0){ return(); } } i++; n--; } will generate the k-element sorted subset A[0]<A[1]<A[2]<...<A[k-1] of {0,1,2,...,n-1}. A more interesting task, which I have not seen before, is to do this in sublinear time. Of course that is only possible with wordwide parallelism. So on a 64-bit machine, if 0<=k<=n<=64, how do we generate a random word whose first n bits contain k ones? We assume computer can do "popcount," "and" and "or" instructions on words in 1 step. Elegant solution: /** This routine, given two 64-bit words L and U, where L is a subset of U (that is, (L and U)==L) and a number k with popcount(L)<=k<=popcount(U), will output a word X which is a random subset of U and superset of L having popcount(X)=k. You can call with L=0 to make a random k-element subset of U, and call with U=complement(0) to get random k-element subsets of 64-element universe. The runtime is O(log(1+popcountU-popcountL)) in expectation. **/ uint64 RandomSubset(int k, uint64 L, uint64 U){ int p; uint64 X; if( k <= popcount(L) ) return(L); if( popcount(U) <= k ) return(U); LoopForever{ X = (randword() and U) or L; p = popcount(X); if( k == p ) return(X); if(k<p){ U=X; }else{ L=X; } } }