C++ – 随机洗牌算法，std::random_shuffle和std::shuffle

1 std::random_shuffle和std::shuffle

std::random_shuffle和std::shuffle处于头文件#include<algorithm>中。

std::random_shuffle和std::shuffle都用于对给定容器范围内的元素重新进行洗牌，打乱顺序重新排序。不过由于std::random_shuffle在迭代器版本（不指定随机函数的情况下）通常依赖std::srand，并且依赖于全局状态，这导致元素洗牌后的不会很理想，所以std::random_shuffle在C++14中已经被弃用，在C++17中被剔除。我们可以使用std::shuffle替代std::random_shuffle。

函数形式

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

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r );

template< class RandomIt, class URBG >
void shuffle( RandomIt first, RandomIt last, URBG&& g );

参数含义

• first : 随机洗牌元素范围第一个元素
• lats：随机洗牌元素范围最后一个元素
• r：返回一个随机选择的可转换类型的值的函数对象
• g：结果类型可转换为UniformRandomBitGenerator的参数

1.1 std::random_shuffle的使用

1.1.1 默认迭代器版本

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>

template <typename T>
void PrintVector(const std::vector<T>& vector)
{
    for_each(vector.begin(), vector.end(), [](T x) {
        std::cout << x << " ";
        });
    std::cout << std::endl;
}


int main()
{
    for (int i = 0; i < 5; ++i)
    {
        std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        std::random_shuffle(vec.begin(), vec.end());
        PrintVector(vec);
    }

    return 0;
}

运行结果：

9 2 10 3 1 6 8 4 5 7
7 5 10 8 4 1 2 9 6 3
3 10 6 4 8 1 7 9 5 2
6 7 10 4 3 2 9 5 1 8
1 3 8 10 7 6 5 2 4 9

1.1.2 指定随机函数

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>

template <typename T>
void PrintVector(const std::vector<T>& vector)
{
    for_each(vector.begin(), vector.end(), [](T x) {
        std::cout << x << " ";
        });
    std::cout << std::endl;
}

int random(int i)
{
    return std::rand() % i;
}


int main()
{
    for (int i = 0; i < 5; ++i)
    {
        std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        std::random_shuffle(vec.begin(), vec.end(),random);
        PrintVector(vec);
    }

    return 0;
}

运行结果：

9 2 10 3 1 6 8 4 5 7
7 5 10 8 4 1 2 9 6 3
3 10 6 4 8 1 7 9 5 2
6 7 10 4 3 2 9 5 1 8
1 3 8 10 7 6 5 2 4 9

从上述两个程序的输出结果上看，在使用默认std::srand()下虽然每一次循环输出的顺序不一样，但是程序内部容器的顺序已经是一样的，这就是std::random_shuffle被弃用的原因。

1.2 std::shuffle的使用

1.2.1 使用非确定性随机整数作为随机种子

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>

template <typename T>
void PrintVector(const std::vector<T>& vector)
{
    for_each(vector.begin(), vector.end(), [](T x) {
        std::cout << x << " ";
        });
    std::cout << std::endl;
}

int main()
{
    for (int i = 0; i < 5; ++i)
    {
        std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        std::random_device rd;
        std::shuffle(vec.begin(), vec.end(), std::default_random_engine(rd()));
        PrintVector(vec);
    }

    return 0;
}

运行结果：

5 2 8 1 6 4 9 10 7 3
4 3 10 9 5 2 6 1 7 8
9 8 3 4 2 5 10 1 6 7
5 1 8 10 4 3 7 2 9 6
5 8 9 4 10 2 1 6 7 3

1.2.2 使用时间作为随机种子

#include <iostream>
#include <random>
#include <algorithm>
#include <vector>
#include <chrono>

template <typename T>
void PrintVector(const std::vector<T>& vector)
{
    for_each(vector.begin(), vector.end(), [](T x) {
        std::cout << x << " ";
        });
    std::cout << std::endl;
}

int main()
{
    for (int i = 0; i < 5; ++i)
    {
        std::vector<int> vec = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
        std::shuffle(vec.begin(), vec.end(), std::default_random_engine(seed));
        PrintVector(vec);
    }

    return 0;
}

运行结果：

8 6 1 4 7 3 10 9 2 5
4 10 1 6 2 8 3 9 5 7
1 8 2 3 4 5 7 6 10 9
9 4 5 10 1 6 7 8 2 3
3 4 9 7 1 6 2 10 5 8

从std::shuffle两个示例的输出结果上看，其输出的容器元素顺序完全不一样，与std::random_shuffle的结果相比，是真正的顺序重排，这就是为什么使用std::shuffle替代std::random_shuffle的原因。