[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.