structural:scholar_edition
Probability: sampling a random combination

There are various algorithms to pick out a random combination from a given set or list. Rejection sampling is extremely slow for large sample sizes. One way to select a k -combination efficiently from a population of size n is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of k − # samples chosen n − # samples visited {\textstyle {\frac {k-\#{\text{samples chosen}}}{n-\#{\text{samples visited}}}}} (see Reservoir sampling). Another is to pick a random non-negative integer less than (n k) {\displaystyle \textstyle {\binom {n}{k}}} and convert it into a combination using the combinatorial number system.