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

C++ – 随机洗牌算法,std::random_shuffle和std::shufflec++

C++

std::random_shufflestd::shuffle

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

std::random_shufflestd::shuffle都用于对给定容器范围内的元素重新进行洗牌,打乱顺序重新排序。不过由于std::random_shuffle在迭代器版本(不指定随机函数的情况下)通常依赖std::srand,并且依赖于全局状态,这导致元素洗牌后的不会很理想,所以std::random_shuffleC++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 );

C++

Copy

参数含义

  • 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;
}

C++

Copy

运行结果:

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

C++

Copy

运行结果:

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

C++

Copy

运行结果:

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

C++

Copy

运行结果:

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的原因。

今天的文章C++ – 随机洗牌算法,std::random_shuffle和std::shuffle分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/33080.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注