`Notes`

`Notes`

```
```[1] This is "Algorithm S" from section 3.4.2 of Knuth (D. E. Knuth, *The Art of Computer Programming. Volume 2: Seminumerical Algorithms* , second edition. Addison-Wesley, 1981). Knuth credits C. T. Fan, M. E. Muller, and I. Rezucha (1962) and T. G. Jones (1962). Note that there are *N! / n! / (N – n)!* ways of selecting a sample of *n* elements from a range of *N* elements. *Random_sample_n* yields uniformly distributed results; that is, the probability of selecting any particular element is *n / N*, and the probability of any particular sampling is *n! * (N – n)! / N!*.

[2] In contrast, the *random_sample* algorithm does not preserve relative ordering within the input range. The other major distinction between the two algorithms is that *random_sample_n* requires its input range to be Forward Iterators and only requires its output range to be Output Iterators, while *random_sample* only requires its input range to be Input Iterators and requires its output range to be Random Access Iterators.