# random_sample_n

Category: algorithms | Component type: function

### Prototype

`Random_sample_n` is an overloaded name; there are actually two `random_sample_n` functions.

    template <class ForwardIterator, class OutputIterator, class Distance>
    OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
                                   OutputIterator out, Distance n)

    template <class ForwardIterator, class OutputIterator, class Distance,
              class RandomNumberGenerator>
    OutputIterator random_sample_n(ForwardIterator first, ForwardIterator last,
                                   OutputIterator out, Distance n,
                                   RandomNumberGenerator& rand)

### Description

`Random_sample_n` randomly copies a sample of the elements from the range `[first, last)` into the range `[out, out + n)`. Each element in the input range appears at most once in the output range, and samples are chosen with uniform probability. [1] Elements in the output range appear in the same relative order as their relative order within the input range. [2]

`Random_sample` copies `m` elements from `[first, last)` to `[out, out + m)`, where `m` is `min(last - first, n)`. The return value is `out + m`.

The first version uses an internal random number generator, and the second uses a Random Number Generator, a special kind of function object, that is explicitly passed as an argument.

### Definition

Defined in the standard header algorithm, and in the nonstandard backward-compatibility header algo.h. This function is an SGI extension; it is not part of the C++ standard.

### Requirements on types

For the first version:

- `ForwardIterator` is a model of Forward Iterator
- `OutputIterator` is a model of Output Iterator
- `ForwardIterator`'s value type is convertible to a type in `OutputIterator`'s set of value types.
- `Distance` is an integral type that is large enough to represent the value `last - first`.

For the second version:

- `ForwardIterator` is a model of Forward Iterator
- `OutputIterator` is a model of Output Iterator
- `RandomNumberGenerator` is a model of Random Number Generator
- `Distance` is an integral type that is large enough to represent the value `last - first`.
- `ForwardIterator`'s value type is convertible to a type in `OutputIterator`'s set of value types.
- `Distance` is convertible to `RandomNumberGenerator`'s argument type.

### Preconditions

- `[first, last)` is a valid range.
- `n` is nonnegative.
- `[first, last)` and `[out, out + n)` do not overlap.
- There is enough space to hold all of the elements being copied. More formally, the requirement is that `[out, out + min(n, last - first))` is a valid range.
- `last - first` is less than `rand`'s maximum value.

### Complexity

Linear in `last - first`. At most `last - first` elements from the input range are examined, and exactly `min(n, last - first)` elements are copied to the output range.

### Example

    int main()
    {
      const int N = 10;
      int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

      random_sample_n(A, A+N, ostream_iterator<int>(cout, " "), 4);
      // The printed value might be 3 5 6 10,
      //  or any of 209 other possibilities.
    }

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

### See also

`random_shuffle`, `random_sample`, Random Number Generator

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation