random_sample_n


类别：算法	组件类型：函数

原型

Random_sample_n是一个重载名称；实际上有这两个random_sample_n函数。

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)

描述

Random_sample_n从范围 [first, last) 中的元素中随机复制一个样本到范围[out, out + n)。输入范围中的每个元素最多在输出范围内出现一次，并且按均匀概率选择样本。[1] 输出范围中的元素按它们在输入范围内的相对顺序出现。[2]Random_sample

复制m从to到范围[out, out + m)，其中是从min(last - first, n)。返回值是out + m第一个版本使用一个内部随机数生成器，而第二个版本使用一个随机数生成器，这是一个特殊类型的函数对象，它被明确地传递为一个参数。.

定义

定义在标准头文件 algorithm 中，以及非标准的后向兼容性头文件 algo.h 中。此函数是 SGI 扩展；它不是 C++ 标准的一部分。

对类型要求

对于第一个版本

ForwardIterator

是前进迭代器的模型OutputIterator
是输出迭代器的模型的值类型可转换为
是前进迭代器的模型的值类型集中的一种类型。是输出迭代器的模型Distance
是一个整数类型，它足够大，可以表示该值last - first对于第二个版本.

RandomNumberGenerator

是前进迭代器的模型OutputIterator
是输出迭代器的模型的值类型可转换为
是随机数生成器的模型可转换为
是一个整数类型，它足够大，可以表示该值last - first对于第二个版本.
是前进迭代器的模型的值类型集中的一种类型。是输出迭代器的模型Distance
是一个整数类型，它足够大，可以表示该值的参数类型。是随机数生成器的模型预处理条件

是一个有效范围。

到范围n
是非负数。和
到范围不重叠。。输入范围中的每个元素最多在输出范围内出现一次，并且按均匀概率选择样本。[1] 输出范围中的元素按它们在输入范围内的相对顺序出现。[2]有足够的空间来容纳所有被复制的元素。更正式地说，要求是
[out, out + min(n, last - first))小于n
对于第二个版本rand的最大值。复杂度

在

中，呈线性关系。最多对于第二个版本来自输入范围的元素被检查，并且恰好对于第二个版本min(n, last - first)个元素被复制到输出范围。示例

备注

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

[1] 这是高德纳第 3.4.2 节中的“算法 S”（D. E. 高德纳，计算机编程的艺术。第 2 卷：半数值算法，第二版。艾迪生-韦斯利出版社，1981 年）。高德纳将功劳记在 C. T. 范、M. E. 穆勒和 I. 雷祖查（1962 年）及 T. G. 琼斯（1962 年）身上。请注意，有

N! / n! / (N - n)!种从范围中选择个是非负数。元素的样本的方法N个元素。Random_sample_n产生均匀分布的结果；也就是说，选择任何特定元素的可能性为n / N，任何特定采样的概率为n! * (N - n)! / N!.

[2] 相比之下，random_sample算法不会保留输入范围的相对顺序。这两种算法的另一个主要区别在于random_sample_n需要其输入范围为向前迭代器，并且仅需要其输出范围为输出迭代器，而random_sample仅需要其输入范围为输入迭代器，并且需要其输出范围为随机访问迭代器。

另请参见

random_shuffle, random_sample，随机数生成器