random_sample


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

原型

Random_sample是重命名的函数；实际上有两个random_sample函数。

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)

描述

Random_sample随机从范围中复制元素样本[first, last)到范围中[ofirst, olast)。输入范围中的每个元素最多在输出范围中出现一次，并且样本以均匀概率选择。[1] 输出范围中的元素可能以任何顺序出现：无法保证保留输入范围内的相对顺序。[2]

Random_sample复制n从元素[first, last)到[ofirst, olast)，其中n为min(last - first, olast - ofirst)。返回值为ofirst + n.

第一个版本使用内部随机数生成器，而第二个版本使用随机数生成器，即一种特殊的函数对象，显式地作为参数传递。

定义

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

类型要求

对于第一个版本

InputIterator是输入迭代器的模型
RandomAccessIterator是随机存取迭代器模型
RandomAccessIterator可变。
InputIterator的值类型可转换为RandomAccessIterator的值类型。

对于第二个版本

InputIterator是输入迭代器的模型
RandomAccessIterator是随机存取迭代器模型
RandomAccessIterator可变。
RandomNumberGenerator是随机数生成器的模型
InputIterator的值类型可转换为RandomAccessIterator的值类型。
RandomAccessIterator的距离类型可转换为RandomNumberGenerator的参数类型。

先决条件

[first, last)是一个有效范围。
[ofirst, olast)是一个有效范围。
[first, last)和[ofirst, olast)不重叠。
last - first小于rand的最大值。

复杂度

以last - first为线性。最多last - first元素从输入范围复制到输出范围。

示例

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

备注

[1] 这是克努斯 3.4.2 部分中“算法 R”（D. E. Knuth，计算机编程的艺术，第 2 卷：半数值算法，第二版。艾迪生-韦斯利，1981 年）。克努斯将功劳归于艾伦·沃特曼。请注意存在N! / n! / (N - n)!从nN元素的范围内选择元素样本的方法。Random_sample生成均匀分布的结果；即，选择任何特定元素的概率为n / N，以及任何特定采样的概率（不考虑元素顺序）为n! * (N - n)! / N!.

[2] 对于您的应用程序而言，如果保留输入范围内的相对顺序很重要，则应使用random_sample_n相反。的主要限制random_sample_n是输入范围必须由前向迭代器而不是输入迭代器组成。

另请参见

random_shuffle, random_sample_n, 随机数生成器