stlab.adobe.com Adobe Systems Incorporated

random_sample_n

algorithms.gif
function.gif
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 RandomNumberGenerator, a special kind of functors, 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 ForwardIterator
  • OutputIterator is a model of OutputIterator
  • 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 ForwardIterator
  • OutputIterator is a model of OutputIterator
  • RandomNumberGenerator is a model of RandomNumberGenerator
  • 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 ForwardIterator and only requires its output range to be OutputIterator, while random_sample only requires its input range to be InputIterator and requires its output range to be RandomAccessIterator.

See also

random_shuffle, random_sample, RandomNumberGenerator

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google