「数组」Knuth洗牌算法|C++random库简单介绍 / LeetCode 384（C++）

给你一个整数数组 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]]

思路

有一个操作，对任意一个元素都可能发生，如果每个元素被操作的概率是相等的，那么这个操作才能公平的进行。

对于数组（长度为len）中每个数字，我们想方法将其中任意一个元素用1/len的概率（等可能）抽出来，然后len--，直到清空数组。我们将元素以拿出的先后顺序为依据形成一个排列，这就是一个公平的随机的排列。

Knuth算法就是一个以此过程对数组进行随机化操作。

算法过程

先介绍C++random（#include <random>）库实现随机数的两个对象。

std::random_device，真随机数类，直接从机器设备中选一个数出来，速度较慢。

std::mt19937,是一个基于32位的梅森旋转算法的对象，生成一个伪随机数，速度较快。

std::random_device rd;实现了一个rd对象。此后每次调用rd()就会获得一个随机数。

std::mt9937 mt(rd()),从rd()调一个随机数作为种子实现了一个mt对象。此后每次调用mt()就会获得一个随机数。

在实际执行Knuth算法中，我们不需要真实取出一个元素，而是只需要初始化i=len-1，从前i+1个数（0,1,2，...i）随机选一个与第i个位置交换即可。

//以------表示随机范围，以*表示取到
     i  0 1 2 3 4
nums[i] 9 8 7 6 5
                i
        ----*----
       ↓       
nums[i] 9 8 5 6 7
              i
        ----*--
       ↓     
nums[i] 9 8 6 5 7
            i
        --*--
       ↓        
nums[i] 9 6 8 5 7
          i
        --*
       ↓   
nums[i] 9 6 8 5 7
        i
        *
       ↓
nums[i] 9 6 8 5 7

std::mt19937 mt;
void Knuth(vector<int>&vec){
     const int len=vec.size();
     for(int i=len-1;i>0;i--)
        swap(vec[mt()%(i+1)], vec[i]);
        //取余操作+1是为了能取到i，因为第i个位置也在备选行列，自己与自己交换也在公平随机之内
}

Code

class Solution {
private:
    vector<int> val;
    mt19937 mt;
    const int len;
 
public:
    Solution(vector<int>& nums) : val(nums), len(nums.size()){};
    vector<int> reset() { return val; }
    vector<int> shuffle() {
        vector<int> ans(val);
        Knuth(ans);
        return ans;
    }
    void Knuth(vector<int>& vec) {
        for (int i = len - 1; i > 0; i--)
            swap(vec[mt() % (i+1) ], vec[i]);
    }
};