1. 前言

随机排列算法，目的是将一个数组中的元素随机打乱随机排列

2. Fisher-Yates洗牌算法

2.1 思路

  1. 获取数组长度为nn

  2. 随机选取[0,n−1][0,n-1]位置上的数据，并与第一个数据交换

  3. 随机选取[1,n−1][1,n-1]位置上的数据，并与第二个数据交换

  4. 重复这个过程

2.2 代码参考


void rand_permutation(const int n,
                                 int *p)
    {
        typedef std::uniform_int_distribution<int> rand_int;
        typedef rand_int::param_type rand_range;
        static std::mt19937_64 gen;
        static rand_int rdi(0, 1);
        int j, k;
        for (int i = 0; i < n; i++)
        {
            p[i] = i;
        }
        for (int i = 0; i < n; i++)
        {
            rdi.param(rand_range(0, n - i - 1));
            j = rdi(gen) + i;
            k = p[j];
            p[j] = p[i];
            p[i] = k;
        }
    }

std::uniform_int_distribution<int> rdi(0, 1)创建一个0到1的均匀分布对象

std::uniform_int_distribution<int>::param_type rand_range 参数范围类型

std::mt19937_64 gen创建随机数生成器

rdi.param(rand_range(0, n-i-1))将分布的范围更改到n−i−1n-i-1