【LeetCode.384打乱数组】Knuth洗牌算法详解

前两天看网易面筋得知网易云的随机歌曲播放使用了这个算法，遂找题来做做学习一下

https://leetcode.cn/problems/shuffle-an-array/

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

Solution(int[] nums) 使用整数数组 nums 初始化对象
int[] reset() 重设数组到它的初始状态并返回
int[] shuffle() 返回数组随机打乱后的结果

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle(); // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset(); // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle(); // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

1 <= nums.length <= 50
-106 <= nums[i] <= 106
nums 中的所有元素都是 唯一的
最多可以调用 104 次 reset 和 shuffle

题目要求的输入是一个整数数组nums，要调用shuffle()函数将其打乱后返回一个乱序数组

（本方法不是重点，想了解直接看后面的代码，LeetCode官解）

一种很古朴的思路是：

再定义一个数组nums4shuffle，把nums中的所有数都存进nums4shuffle，然后遍历nums4shuffle

假设当前循环变量是i，此时从nums4shuffle中随机选取一个数，作为打乱后的nums的第i个元素

那么要解决的问题有以下几个：

1、如何再次获取数组的初始顺序

2、如何从nums4shuffle中随机取值

Fisher-Yates 洗牌算法

在上述问题中，所谓的“打乱”（或者说随机洗牌），其实可以理解为：让每一个元素都等概率地出现在每一个位置

即每个位置都能等概率的放置每个元素

听上去有点耳熟？Knuth 洗牌算法实际上就是一种将数组中元素随机排列的组合问题。

假设有一个长度为 n 的数组 arr，我们需要对其进行随机化操作，使得其中的每个元素都具有相等的可能性出现在任意位置上。这可以理解为是从 n 个元素中选择 n 个元素不重复地排列的问题，即全排列。因此，根据组合数学的知识，共有 n! 种不同的可能性，每一种可能性出现的概率应该是相等的，即为 1/n!。

因此，Knuth 洗牌算法的正确性在于它能够保证每个排列出现的概率相等，并且所有可能的排列构成了一个大小为 n! 的集合。这与概率论中的组合问题有着相似的思路和方法。

该算法使用代码实现起来很简洁，就是一个for循环即可

void knuth_shuffle(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n; ++i) {
        // 随机选择一个位置 j，其中 i <= j < n
        int j = rand() % (n - i) + i;
        // 交换 arr[i] 和 arr[j] 的值
        swap(arr[i], arr[j]);
    }
}

knuth_shuffle 函数是用于执行 Knuth 洗牌算法的函数，它接受一个整数类型的数组 arr 作为输入参数，使用该算法对数组进行随机化操作。

函数中首先获取数组的长度 n，然后开始遍历数组。在每一轮遍历中，函数会随机选择一个位置 j，其中 i <= j < n，也就是从 i 开始到数组末尾之间随机选择一个位置。

这里使用了 rand() 函数来生成随机数，并将其除以取模运算的余数与 i 相加，得到最终的位置 j, rand() 函数默认生成的随机数范围是 0 到 RAND_MAX（通常为 32767）。

假设n=5，i=2，此时已经到了第二轮循环，前两个数已经被随机交换，现在要在剩下的3个数中进行交换

rand()函数会生成0到32767之间的一个随机整数，我们将它除以(n-i)=3，然后取余数

假设rand()生成的随机整数为10000，则它除以3的结果是3333余1。以此类推，我们就可能得到0~2之间的余数

当前遍历到的位置是2，那么只要在加上2就可以得到一个2~4之间的随机数

根据上面的分析，j的结果就是n - i之间的一个随机数

一旦选定了位置 j，函数就会交换 arr[i] 和 arr[j] 这两个元素的值。

这样，每一次遍历都会使得数组中的某个元素被随机地交换到前面的位置上，从而实现了 Knuth 洗牌算法的效果

class Solution {
public:
    Solution(vector<int>& nums) {        
        nums4save = nums;//初始化nums4save
    }
    
    vector<int> reset() {
        return nums4save;//重置数组时只要返回保存的初始数组即可
    }
    
    vector<int> shuffle() {
        vector<int> nums4shuffle = nums4save;//定义一个新数组用于打乱顺序
        int numsLen = nums4shuffle.size();
        //洗牌算法
        for(int i = 0; i < numsLen; ++i){//通过for循环选取一个数
        //在(i,numsLe]间再随机选择一个数与for循环选择的数进行交换
            int random = rand() % (numsLen - i) + i;//计算numsLen - i之间的一个随机数
            swap(nums4shuffle[i], nums4shuffle[random]);//交换
        }
        return nums4shuffle;//返回打乱后的数组
    }
private:
    vector<int> nums4save;//定义nums4save用于保存初始数组
};

class Solution {
public:
    Solution(vector<int>& nums) { // 构造函数
        // 将传入的nums保存到成员变量this->nums中
        this->nums = nums;
        // 创建一个与nums等长的vector original，并将nums的值复制到original中
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() { // 还原为原始顺序
        // 将original中的元素值复制到nums中
        copy(original.begin(), original.end(), nums.begin());
        // 返回nums
        return nums;
    }
    
    vector<int> shuffle() { // 随机打乱顺序
        // 创建一个新的vector shuffled，用于保存随机打乱后的nums
        vector<int> shuffled = vector<int>(nums.size());
        // 创建一个list lst，并将nums中的元素值复制到lst中
        list<int> lst(nums.begin(), nums.end());
      
        // 遍历nums
        for (int i = 0; i < nums.size(); ++i) {
            // 在lst的元素个数范围内生成一个随机索引j
            int j = rand()%(lst.size());
            // 获取lst中索引为j的元素，并将其赋值给shuffled[i]
            auto it = lst.begin();
            advance(it, j);//将迭代器 it 向前移动 j 个位置，就可以获得对应的随机元素
            shuffled[i] = *it;
            // 从lst中删除索引为j的元素
            lst.erase(it);
        }
        // 将shuffled中的元素值复制到nums中
        copy(shuffled.begin(), shuffled.end(), nums.begin());
        // 返回nums
        return nums;
    }
private:
    vector<int> nums; // 原始数组
    vector<int> original; // 原始顺序
};