Efficient n-choose-k random sampling
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:


Let arr be an array of size $n$ and a default value that is not True.
Let out be an empty array.
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.
Go back to 3 unless we have selected $k$ elements.
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.