random_shuffle

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

原型

template <class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rand)

说明

方法定义

对类型的要求

• RandomAccessIterator是 随机访问迭代器 的模型

• RandomAccessIterator是 随机访问迭代器 的模型
• RandomNumberGenerator是 随机数生成器 的模型
• RandomAccessIterator的距离类型可转换为RandomNumberGenerator的参数类型。

预处理条件

• [第一个，最后一个)是一个有效的范围。
• 最后一个 - 第一个小于rand的最大值。

复杂度

示例

const int N = 8;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
random_shuffle(A, A + N);
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The printed result might be 7 1 6 3 2 5 4 8, 
//  or any of 40,319 other possibilities.

说明

[1] 此算法在 Knuth (D. E. Knuth, 计算机编程的艺术。第 2 卷：半数算法，第二次编辑。Addison-Wesley，1981 年）的 3.4.2 节中进行了描述。Knuth 提到了 Moses 和 Oakford (1963 年) 和 Durstenfeld (1964 年) 的功劳。注意，有 N! 方法可以排列 N 元素的序列。Random_shuffle生成均匀分布的结果；也就是说，任何特定排序的概率为 1/N!。此注释很重要的原因在于，许多算法乍一看似乎实现了序列的随机改组，但实际上并未在 N! 可能的排序中产生均匀分布。也就是说，很容易错误地进行随机改组。

另请参见