random_sample
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
Wyszukiwarka
Podobne podstrony:
random sample nTOEIC Listening and Reading Sample Testshortcuts sampleSampleLog sampleDragonfly (sample)Random?ts of Kindnessbaby sampler3 misiabeKewlPack #2 SamplesFirst 2015 Listening sample paperdxf sampleCondor (sample)randomsampleEmbedCodewięcej podobnych podstron