# random_sample

Category: algorithms | Component type: function

### Prototype

`Random_sample` is an overloaded name; there are actually two `random_sample` functions.

    template <class InputIterator, class RandomAccessIterator>
    Random AccessIterator
    random_sample(InputIterator first, InputIterator last,
    	      RandomAccessIterator ofirst, RandomAccessIterator olast)

    template <class InputIterator, class RandomAccessIterator,
    	  class RandomNumberGenerator>
    random_sample(InputIterator first, InputIterator last,
    	      RandomAccessIterator ofirst, RandomAccessIterator olast,
    	      RandomNumberGenerator& rand)

### Description

`Random_sample` randomly copies a sample of the elements from the range `[first, last)` into the range `[ofirst, olast)`. 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 might appear in any order: relative order within the input range is not guaranteed to be preserved. [2]

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

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:

- `InputIterator` is a model of Input Iterator
- `RandomAccessIterator` is a model of Random Access Iterator
- `RandomAccessIterator` is mutable.
- `InputIterator`'s value type is convertible to `RandomAccessIterator`'s value type.

For the second version:

- `InputIterator` is a model of Input Iterator
- `RandomAccessIterator` is a model of Random Access Iterator
- `RandomAccessIterator` is mutable.
- `RandomNumberGenerator` is a model of Random Number Generator
- `InputIterator`'s value type is convertible to `RandomAccessIterator`'s value type.
- `RandomAccessIterator`'s distance type is convertible to `RandomNumberGenerator`'s argument type.

### Preconditions

- `[first, last)` is a valid range.
- `[ofirst, olast)` is a valid range.
- `[first, last)` and `[ofirst, olast)` do not overlap.
- `last - first` is less than `rand`'s maximum value.

### Complexity

Linear in `last - first`. At most `last - first` elements are copied from the input range to the output range.

### Example

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

      random_sample(A, A+N, B, B+n);
      copy(B, B + n, ostream_iterator<int>(cout, " "));
      // The printed value might be 1 6 3 5,
      //  or any of 5039 other possibilities.
    }

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

### See also

`random_shuffle`, `random_sample_n`, Random Number Generator

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