【LeetCode.384打亂陣列】Knuth洗牌演演算法詳解

前兩天看網易麵筋得知網易雲的隨機歌曲播放使用了這個演演算法，遂找題來做做學習一下

打亂陣列

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

給你一個整數陣列 nums ，設計演演算法來打亂一個沒有重複元素的陣列。打亂後，陣列的所有排列應該是 等可能 的。

實現 Solution class:

Solution(int[] nums) 使用整數陣列 nums 初始化物件
int[] reset() 重設陣列到它的初始狀態並返回
int[] shuffle() 返回陣列隨機打亂後的結果

範例 1：

輸入
["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; // 原始順序
};