c++ STL随机算法:random_shuffle()详解

云计算 2024年11月22日 10:13 3 admin

C++标准模板库(STL)中的randoM_shuFFle算法提供了一种简便的方式来随机重新排列容器或数组中的元素顺序。然而，值得注意的是，自从C++14起，random_shuffle已被弃用，并在C++17中被彻底移除，推荐使用std::shuffle代替，因为shuffle提供了更清晰的接口和更强的随机性控制。尽管如此，了解random_shuffle的工作原理仍然有助于深入理解C++随机化算法的设计思想。

random_shuffle 简介

在C++98/03标准中，random_shuffle是<Algorithm>头文件中的一部分，其主要目的是对给定的序列进行随机重新排序，常用于模拟随机抽样、游戏卡牌洗牌等场景。random_shuffle函数的基本形式如下：

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

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

第一个版本使用默认的随机数生成器（通常是全局的rand()函数），而第二个版本允许用户指定随机数生成器，这为算法提供了更高的灵活性和控制力。

工作原理

random_shuffle算法的核心在于Fisher-Yates洗牌算法，这是一种高效且公平的随机排列生成算法，确保每个排列出现的概率相等。算法步骤大致如下：

初始化：从序列的最后一个元素开始，设索引为i = last - first - 1。
随机选择：为当前位置i选取一个索引j，其中0 <= j <= i。这个索引j是通过随机数生成器产生的。
交换：交换位置i和j处的元素。
递减索引：i -= 1，重复步骤2-3直到i = 0。

使用示例

以下是一个使用random_shuffle（尽管已废弃，但为理解原理）的例子：

#include <algorithm> // 包含random_shuffle
#include <vector>
#include <iostream>
#include <cTime> // 包含time，用于设置随机数种子
#include <cstdlib> // 包含srand和rand

int mAIn() {
    srand(time(0)); // 设置随机数种子，确保每次运行程序时随机性不同

    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    std::cout << "Before shuffling: ";
    for(int n : numbers) std::cout << n << " ";
    std::cout << std::endl;

    std::random_shuffle(numbers.begin(), numbers.end());

    std::cout << "After shuffling: ";
    for(int n : numbers) std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}

迁移到std::shuffle

鉴于random_shuffle的废弃，推荐使用std::shuffle，它位于同一个<algorithm>头文件中。std::shuffle的一个显著改进是它明确要求用户提供一个高质量的随机数生成器，如std::mt19937，这能生成更均匀的随机分布，提高随机化的质量。

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

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto rng = std::default_random_engine(std::chrono::system_cloCK::now().time_since_epoch().count());

    std::cout << "Before shuffling: ";
    for(int n : numbers) std::cout << n << " ";
    std::cout << std::endl;

    std::shuffle(numbers.begin(), numbers.end(), rng);

    std::cout << "After shuffling: ";
    for(int n : numbers) std::cout << n << " ";
    std::cout << std::endl;

    return 0;
}