前言

洗牌算法是项目开发中常用的一种算法，它和随机数有着密不可分的关系，比如我们从报名参与活动的前10个用户中选取一个人发放幸运奖，这时可以从[1, 10] 范围内随机一个数来确定幸运儿；如果是抽取两个人呢？那就随机两次！是的，确实可以这样做，但是随着随机次数的增多，后面随机的数字很可能和前面一样，这时就要重复随机才能解决。

想想现实生活中我们可以怎么做，取红桃A-红桃10一共10张扑克牌，然后把它们随机洗一洗牌，如果需要取3个幸运儿，那么只需取扑克牌的前三张就可以了，这样很容易就取到了不重复的3个数字，当然你从中间随机抽取也是可以的，这样操作在逻辑实现上要复杂一点点。

洗牌算法

其实洗牌利用的是一个排列的概念，学过排列组合的知识以后我们很清楚，n个元素排列的种类数一共是:

$$
A^n_n
$$

也就是n!，这是个恐怖的数字，比如打印N个数字的全排列，它的是时间复杂度就是O(N!)，这个谁也没办法优化，因为打印这些排列情况就需要O(N!)这么多的时间，而洗牌就是保证从这些元素组成的全排列中等概率的选取一种排列。

把所有的排列情况列举出来，然后从中选择一个所需时间是O(N!)，这显然是不现实的，所以很多大神们进行了优化，出现了多种洗牌算法，下面我只列举一种比较好理解的 Knuth-Durstenfeld Shuffle 算法。

改洗牌算法可简单表述为：一个拥有n个元素的初始序列，将最后一个数和该序列的前 n 个数中的随机一个数进行交换（如果随机结果是和第n个数交换，相当于没换），然后倒数第二个数和该序列的前 n - 1 个数中的随机一个数进行交换，以此类推，直到将该序列第一个数操作完，就完成了洗牌，该算法保证了每个元素在每个位置的概率都是相等的，时间复杂度为O(N)。

举个例子就像下面这样：

初始序列是 A、B、C、D、E、F，为了便于和刚才的算法思路对应描述，索引从1开始

第一轮从1-6个位置中随机一个和最后的 F 交换，假如随机到位置3，也就是和 C 交换，结果为：

A B F D E C

概率是P=1/6，也就是随机一个数字的概率

第二轮从1-5个位置中随机一个和倒数第二个元素 E 交换，假如随机到的是位置2，也就是和 B 交换，结果为：

A E F D B C

概率是P=(5/6)*(1/5)=1/6，为什么这么算呢？要想和 B 交换必须第一轮随机不到B才可以，所以要在前面乘以 5/6

第三轮从1-2个位置中随机一个和倒数第二个元素 D 交换，假如随机到的还是位置2，也就是和 E 交换，结果为

A D F E B C

概率是P=(5/6)*(4/5)*(1/4)=1/6，有了第二轮这个就应该明白了吧

依次类推，直到操作完第五次随机交换，整个洗牌算法也就完成了，伪代码也就几行

for (int i = vec.size() - 1; i > 0; i--)
{
    std::swap(vec[i], vec[std::rand() % (i + 1)]);
}

std::random_shuffle

使用这个函数需要引用头文件 <algorithm>，共有以下几个重载函数：

template< class RandomIt >
void random_shuffle( RandomIt first, RandomIt last ); //(deprecated in C++14)(removed in C++17)

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc& r );  //(until C++11)
                                            //(deprecated in C++14)(removed in C++17)

template< class RandomIt, class RandomFunc >
void random_shuffle( RandomIt first, RandomIt last, RandomFunc&& r ); //(since C++11)
                                            //(deprecated in C++14)(removed in C++17)

从文档来看 std::random_shuffle 这个函数的实现在C++14标准中已经不推荐使用，在C++17中已经被移除了，函数定义如下：

/**
   *  @brief Randomly shuffle the elements of a sequence.
   *  @ingroup mutating_algorithms
   *  @param  __first   A forward iterator.
   *  @param  __last    A forward iterator.
   *  @return  Nothing.
   *
   *  Reorder the elements in the range @p [__first,__last) using a random
   *  distribution, so that every possible ordering of the sequence is
   *  equally likely.
  */
  template<typename _RandomAccessIterator>
    inline void
    random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first != __last)
      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
      {
        // XXX rand() % N is not uniformly distributed
        _RandomAccessIterator __j = __first
                    + std::rand() % ((__i - __first) + 1);
        if (__i != __j)
          std::iter_swap(__i, __j);
      }
    }

  /**
   *  @brief Shuffle the elements of a sequence using a random number
   *         generator.
   *  @ingroup mutating_algorithms
   *  @param  __first   A forward iterator.
   *  @param  __last    A forward iterator.
   *  @param  __rand    The RNG functor or function.
   *  @return  Nothing.
   *
   *  Reorders the elements in the range @p [__first,__last) using @p __rand to
   *  provide a random distribution. Calling @p __rand(N) for a positive
   *  integer @p N should return a randomly chosen integer from the
   *  range [0,N).
  */
  template<typename _RandomAccessIterator, typename _RandomNumberGenerator>
    void
    random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
#if __cplusplus >= 201103L
           _RandomNumberGenerator&& __rand)
#else
           _RandomNumberGenerator& __rand)
#endif
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
        _RandomAccessIterator>)
      __glibcxx_requires_valid_range(__first, __last);

      if (__first == __last)
        return;
      for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
        {
            _RandomAccessIterator __j = __first + __rand((__i - __first) + 1);
            if (__i != __j)
                std::iter_swap(__i, __j);
        }
    }

以上函数实现来源于文件 /usr/include/c++/5/bits/stl_algo.h，看源码时发现一个问题，原来标准库中的代码也是空格和Tab混用，复制过来的时候我还专门整理了一下。

第一个仅两个参数的函数中首先验证了迭代器的类型和范围的有效性，同时使用了 std::rand() 函数来随机选择了一个需要交换的元素，而拥有三个参数的函数逻辑几乎一样，只是使用了自定义传入的随机函数来选择需要交换的元素，所以洗牌算法的核心逻辑就是这个随机函数。

rand 和 srand

这两个是C标准函数，在C++中被放在头文件 <cstdlib> 之中，搜索到的函数声明如下：

__BEGIN_NAMESPACE_STD
/* Return a random integer between 0 and RAND_MAX inclusive.  */
extern int rand (void) __THROW;
/* Seed the random number generator with the given number.  */
extern void srand (unsigned int __seed) __THROW;
__END_NAMESPACE_STD

其中 std::rand() 是用于返回一个介于[0, RAND_MAX] 范围的伪随机整型值，RAND_MAX 的值最小为 32767，也就是有符号short的最大值，我查到的版本库中的值是2147483647，即有符号int的最大值。

std::srand() 的作用是为 st::rand() 这个伪随机数生成器设置种子，如果在调用 std::srand() 之前使用了 std::rand()，种子默认为1，相当于调用了 std::srand(1)，rand通常不是线程安全的函数，依赖于具体的实现。

另外你可能还见过 random 和 srandom 等函数，他们通常是另一个标准（BSD）的随机函数，比如下面这段描述：

/* These are the functions that actually do things.  The `random', `srandom',
   `initstate' and `setstate' functions are those from BSD Unices.
   The `rand' and `srand' functions are required by the ANSI standard.
   We provide both interfaces to the same random number generator.  */
/* Return a random long integer between 0 and RAND_MAX inclusive.  */
extern long int random (void) __THROW;

/* Seed the random number generator with the given number.  */
extern void srandom (unsigned int __seed) __THROW;

如果是在 POSIX 平台你可能还会遇到 rand_r(int *seed) 函数。

需要注意的是， std::rand() 生成的是一个伪随机序列，如果随机种子相同，则得到的序列也是相同的，这也是 std::rand 不建议使用的原因，建议是使用C++11随机数生成工具来替换它。

伪随机序列也并不是“一无是处”，两个进程可以通过设置相同的随机数种子来产生相同的序列，比如可以用于服务器和客户端做帧同步时产生随机数，这样的随机数产生是同步可控的。

下面举个 std::rand() 使用的例子

#include <iostream>
#include <cstdlib>

int main()
{
    std::srand(1);
    std::cout << std::rand() << std::endl;

    std::srand(1);
    std::cout << std::rand() << std::endl;

    std::srand(1);
    std::cout << std::rand() << std::endl;

    return 0;
}

运行结果如下：

albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
1804289383
1804289383
1804289383

我们可以看到因为随机种子相同，生成的随机数都是同一个，为了使的生成的序列更随机，通常使用当前时间戳 std::time(nullptr) 作为随机种子，然后再生成随机序列：

#include <iostream>
#include <cstdlib>
#include <ctime>

int main()
{
    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;

    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;

    std::srand(std::time(nullptr));
    std::cout << std::rand() << std::endl;

    return 0;
}

运行结果如下：

albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
1777572541
1777572541
1777572541

怎么还是相同的呢？那是因为 std::time(nullptr) 函数返回的时间戳单位是秒，在一秒中内的时间种子是相同的，所以返回的序列也是相同的，通常的使用方法是在程序启动时设置一次时间种子就可以了，并不需要每次都进行设置，而 random_shuffle 中使用了 std::rand() 函数，如果不手动设置时间种子，每次同一时间洗同一副牌，得到的结果也是相同的，所以这也是random_shuffle被后续版本移除的一个原因。

随机数生成器和分布器

random是C++11提供的一个头文件，其中包含多个随机数生成工具，可以使用生成器和分布器的组合产生随机数，其中包含随机数生成器和分布器的多个类实现，分为以下两种：

Uniform random bit generators (URBGs)：均匀随机位生成器，也就是生成均匀分布随机数的对象，可以生成伪随机序列，也可生成真正的随机数序列
Random number distributions：随机数分布器，用于将URBGs产生的随机数转换为某种特定数学概率分布的序列，如均匀分布、正态分布、泊松分布等

常见的生成器：

linear_congruential_engine: 线性同余生成算法，是最常用也是速度最快的，随机效果一般
mersenne_twister_engine: 梅森旋转算法，随机效果最好
subtract_with_carry_engine: 滞后Fibonacci算法

常见的适配器，我理解的它的作用是生成器的二次加工厂，对生成器结果进行特定操作

discard_block_engine: 丢弃一些数
independent_bits_engine: 将序列打包成指定位数的块
shuffle_order_engine: 调整序列顺序

预定义的随机数生成器，利用通用生成器和适配器组合出的流行特定生成器：

minstd_rand
minstd_rand0
mt19937: mt是因为这个伪随机数产生器基于Mersenne Twister算法，19937来源于产生随的机数的周期长可达到2^19937-1。
mt19937_64
ranlux24_base
ranlux48_base
ranlux24
ranlux48
knuth_b
default_random_engine: 编译器可以自行实现

以上随机数引擎需要一个整型参数作为种子，对于给定的随机数种子，伪随机数生成器总会生成相同的序列，这在测试的时候是相当有用的。而在实际使用时，需要设置随机树作为种子来产出不同的随机数，推荐使用 std::random_device 的值作为随机数种子。

std::random_device 是一个使用硬件熵源的非确定性随机数发生器，不可预测。

常见的分布器：

uniform_int_distribution: 均匀离散分布
uniform_real_distribution: 均匀实数分布
bernoulli_distribution: 伯努利分布
binomial_distribution: 二项式分布
geometric_distribution: 几何分布
negative_binomial_distribution: 负二项式分布
poisson_distribution: 泊松分布
exponential_distribution: 指数分布
gamma_distribution: 伽玛分布
weibull_distribution: 威布尔分布
extreme_value_distribution: 极值分配
normal_distribution: 正态分布
lognormal_distribution: 对数正态分布
chi_squared_distribution: 卡方分布
cauchy_distribution: 柯西分布
fisher_f_distribution: Fisher F分布
student_t_distribution: 学生T分布
discrete_distribution: 离散分布
piecewise_constant_distribution: 分段常数分布
piecewise_linear_distribution: 分段线性分布

下面举个生成器和分布器组合生成随机常用例子，以下为模拟掷骰子生成点数的实现：

#include <iostream>
#include <random>

int main()
{
    std::mt19937 gen(std::random_device{}());
    std::uniform_int_distribution<> dist(1, 6);

    for (int i = 0; i < 10; ++i)
        std::cout << dist(gen) << std::endl;

    return 0;
}

编译运行结果如下：

albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
3
2
4
1
5
4
1
1
3
4

std::shuffle

终于又转回来了，去随机数那一块儿溜了半天，终于回到了洗牌函数，这个函数是C++11版本才加入的，函数定义如下：

/**
 *  @brief Shuffle the elements of a sequence using a uniform random
 *         number generator.
 *  @ingroup mutating_algorithms
 *  @param  __first   A forward iterator.
 *  @param  __last    A forward iterator.
 *  @param  __g       A UniformRandomNumberGenerator (26.5.1.3).
 *  @return  Nothing.
 *
 *  Reorders the elements in the range @p [__first,__last) using @p __g to
 *  provide random numbers.
*/
template<typename _RandomAccessIterator,
     typename _UniformRandomNumberGenerator>
  void
  shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last,
      _UniformRandomNumberGenerator&& __g)
  {
    // concept requirements
    __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
      _RandomAccessIterator>)
    __glibcxx_requires_valid_range(__first, __last);

    if (__first == __last)
  return;

    typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  _DistanceType;

    typedef typename std::make_unsigned<_DistanceType>::type __ud_type;
    typedef typename std::uniform_int_distribution<__ud_type> __distr_type;
    typedef typename __distr_type::param_type __p_type;
    __distr_type __d;

    for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
  std::iter_swap(__i, __first + __d(__g, __p_type(0, __i - __first)));
  }

这种实现和之前 std::random_shuffle 函数实现很类似，只是随机数部分有些不同，它的第3个参数需要的是一个均匀随机数生成器URBGs，一个常见的使用方法如下：

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

int main()
{
    std::vector<int> vec{1, 2, 3, 4, 5, 6};

    std::mt19937 gen(std::random_device{}());
    std::shuffle(vec.begin(), vec.end(), gen);

    std::copy(vec.begin(), vec.end(), std::ostream_iterator<int>(std::cout, " "));

    return 0;
}

编译后运行结果如下：

1
2
3

albert@home-pc:/mnt/d/data/cpp/testrandom$ g++ testrandom.cpp --std=c++11
albert@home-pc:/mnt/d/data/cpp/testrandom$ ./a.out
3 5 1 2 6 4

randint

结尾了顺便说一下偶然看到的一个实验性函数 std::experimental::randint，用于生成指定范围内的一个随机数，目前还没有进入标准，不过看起来使用很方便了，后续有可能被纳入标准吧，贴一下 cppreference 上的例子 std::experimental::randint 如下：

#include <iostream>
#include <experimental/random>

int main()
{
    int random_number = std::experimental::randint(100, 999);
    std::cout << "random 3-digit number: " << random_number << '\n';
}

总结

std::random_shuffle 可以只传递一个待洗牌的区间，函数内会使用默认的 std::rand 函数来完成随机元素的选择，依赖全局状态
std::random_shuffle 也可以传入自定义的随机函数，不过这个函数在C++14表中已经不建议时使用了，在C++17标准中已经被移除
std::shuffle 是C++11标准添加的，也是推荐使用的洗牌函数，它的第三个参数需要传递一个均匀随机数生成器对象
C++11中的<random>头文件中提供了很多生成随机数的工具，需要搭配生成器和分布器来使用
mt19937 名字看起来有点怪，但它是常用的生成器，mt表示它基于Mersenne Twister算法，19937源于产生随的机数的周期长可达到2^19937-1

==>> 反爬链接，请勿点击，原地爆炸，概不负责！<<==

当被误解时，解释或者争论都是没有用的，有些事情就解释不清楚，或者根本无法解释，甚至没有人会听你解释，想一想，真的什么也做不了，就像一句名言说的，你永远叫不醒一个装睡的人，那个故意误解你的人又怎会听你解释~

2022-5-3 21:02:56