std::random_shuffle, std::shuffle

来自cppreference.com
< cpp‎ | algorithm
 
C++
 
算法库
受约束算法及范围上的算法 (C++20)
受约束算法： std::ranges::copy, std::ranges::sort, ...
执行策略 (C++17)
不修改序列的操作
(C++11)(C++11)(C++11)
(C++17)
修改序列的操作
Partitioning operations
划分操作
排序操作
(C++11)
(C++11)
二分搜索操作
集合操作（在已排序范围上）
堆操作
(C++11)
(C++11)
最小/最大操作
(C++11)
(C++11)
(C++17)

排列
数值运算
未初始化存储上的操作
(C++17)
(C++17)
(C++17)
(C++20)
C 库
 
在标头 <algorithm> 定义
template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last );
 (1) (C++14 中弃用)
(C++17 中移除)
(2)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );
 (C++11 前)
template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );
 (C++11 起)
(C++14 中弃用)
(C++17 中移除)
template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );
 (3) (C++11 起)

重排序给定范围 [first, last) 中的元素，使得这些元素的每个排列拥有相等的出现概率。

1) 随机来源由实现定义，但经常会使用函数 std::rand。
2) 随机来源是函数对象 r。
3) 随机来源是对象 g。

参数

first, last - 要随机打乱的元素范围
r - 函数对象。如果以 r(n) 调用，那么返回可转换到 std::iterator_traits<RandomIt>::difference_type 的在区间 [​0​, n) 中随机选取的值
g - 均匀随机位生成器 (UniformRandomBitGenerator) ，它的结果类型可隐式转换到 std::iterator_traits<RandomIt>::difference_type
类型要求
-
RandomIt 必须符合值可交换 (ValueSwappable) 和 老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
-
std::remove_reference_t<URBG> 必须符合均匀随机位生成器 (UniformRandomBitGenerator) 的要求。

返回值

（无）

复杂度

与 first 和 last 间的距离呈线性。

注意

标准未指定实现，所以即使你用准确相同的 RandomFunc 或 URBG，也可能通过不同的标准库实现得到不同结果。

可能的实现

也可以参考 libstdc++ and libc++ 的实现。

random_shuffle (1) 
template<class RandomIt>
void random_shuffle(RandomIt first, RandomIt last)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
 
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[std::rand() % (i + 1)]);
        // rand() % (i + 1) 实际上不准确，因为生成的数对于多数 i 值不均匀分布。
        // 正确实现将实际上需要重新实现 C++11 std::uniform_distributtion，
        // 这超出了此示例的范畴。
    }
}
random_shuffle (2) 
template<class RandomIt, class RandomFunc>
void random_shuffle(RandomIt first, RandomIt last, RandomFunc&& r)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
 
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[r(i + 1)]);
    }
}
shuffle 
template<class RandomIt, class URBG>
void shuffle(RandomIt first, RandomIt last, URBG&& g)
{
    typedef typename std::iterator_traits<RandomIt>::difference_type diff_t;
    typedef std::uniform_int_distribution<diff_t> distr_t;
    typedef typename distr_t::param_type param_t;
 
    distr_t D;
    for (diff_t i = last - first - 1; i > 0; --i)
    {
        using std::swap;
        swap(first[i], first[D(g, param_t(0, i))]);
    }
}

示例

下列代码随机打乱整数 1~10：

运行此代码
#include <random>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
 
int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
 
    std::random_device rd;
    std::mt19937 g(rd());
 
    std::shuffle(v.begin(), v.end(), g);
 
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
}

可能的输出： 

8 6 10 4 2 3 7 1 9 5

Defect reports

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
LWG 395 C++98 未指定重载 (1) 的随机来源，而且
std::rand 由于 C 库的要求不能作为来源 		由实现定义，并且可以将
std::rand 作为来源
LWG 552 C++98 不要求重载 (2) 的随机来源是 r[1] 要求是
  1. ↑ 重载 (3) 也有同样的缺陷，但那部分的解决方案不适用于 C++98。

参阅

 产生某个元素范围的按字典顺序的下一个较大的排列
(函数模板)
产生某个元素范围的按字典顺序的下一个较小的排列
(函数模板)
(C++20)
 随机重排范围中的元素
(niebloid)
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/algorithm/random_shuffle&oldid=76878”