`Notes`

`Notes`

```
```[1] This is "Algorithm R" 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 Alan Waterman. Note that there are *N! / n! / (N – n)!* ways of selecting a sample of *n* elements from a range of *N* elements. *Random_sample* yields uniformly distributed results; that is, the probability of selecting any particular element is *n / N*, and the probability of any particular sampling (not considering order of elements) is *n! * (N – n)! / N!*.

[2] If preservation of the relative ordering within the input range is important for your application, you should use *random_sample_n* instead. The main restriction of *random_sample_n* is that the input range must consist of Forward Iterators, rather than Input Iterators.