| |
|
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);
}
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