leetcode384. 打亂數組

傳送門

題目:打亂一個沒有重複元素的數組。

示例:
// 以數字集合 1, 2 和 3 初始化數組。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打亂數組 [1,2,3] 并傳回結果。任何 [1,2,3]的排列傳回的機率應該相同。
solution.shuffle();
// 重設數組到它的初始狀态[1,2,3]。
solution.reset();
// 随機傳回數組[1,2,3]打亂後的結果。
solution.shuffle();
           

一、使用:随機亂置算法（洗牌算法）。

最常用的洗牌算法。因為該算法的細節容易出錯，且存在好幾種變體，雖有細微差異但都是正确的，

是以這裡隻介紹一種簡單的。

此類算法都是靠随機選取元素交換來擷取随機性，直接看代碼（僞碼）

得到一個在在左開右閉區間 [min, max) 内的随機整數

int randNum(int min, int max)

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        int rand = randNum(i, n); // 從 i 到最後随機選一個元素
        swap(arr[i], arr[rand]);
    }
}
           

分析洗牌算法正确性的準則：産生的結果必須有 n! 種可能，否則就是錯誤的。
這個很好解釋，因為一個長度為 n 的數組的全排列就有 n! 種，也就是說打亂結果總共有 n! 種。
洗牌算法 每次生成随機的左邊界是i,每次都進1

i=0: 第1次選擇 有 n次選擇(0到n-1)
i=1: 第2次選擇 有n-1次選擇(1到n-1)
i=2: 第3次選擇 有n-2次選擇(2到n-1)……    顯然是:   n!

是以下面這種做法是錯的, 因為左邊界一直沒變 
跟i交換的索引一直是n種選擇 是以有n*n*n…n (n的n次方)種

錯誤的索引生成方法：int rand = randInt(0, n); // 每次都從區間 [0, n)中随機選取元素進行交換
           

二、蒙特卡羅方法驗證正确性

洗牌算法，正确性衡量标準是:

對于每種可能的結果出現的機率必須相等，也就是說要足夠随機。

如果不用數學嚴格證明機率相等，可以用蒙特卡羅方法近似地估計出機率是否相等，結果是否足夠随機。

我們可以對同一個數組進行一百萬次洗牌，統計各種結果出現的次數，把頻率作為機率，可以很容易看出洗牌算法是否正确。整體思想很簡單，不過實作起來也有些技巧的：

每次進行洗牌算法後，就把得到的打亂結果對應的頻數加一，重複進行 100 萬次，如果每種結果出現的總次數差不多，那就說明每種結果出現的機率應該是相等的。作為一種驗證方法，我們不需要 n 太大，一般用長度為 5 或 6 的 arr 試下就差不多了: 這個思路的僞代碼：

void shuffle(int[] arr);

// 蒙特卡羅
int N = 1000000;
HashMap count; // 作為直方圖
for (i = 0; i < N; i++) {
    int[] arr = {1,2,3};
    shuffle(arr);
    // 此時 arr 已被打亂
    count[arr] += 1；
}
for (int feq : count.values()) 
    print(feq / N + " "); // 頻率
           

------------------------------------------ AC代碼 --------------------------------------

int[] copyArray;// 用來交換的拷貝數組
    int[] originalArray;// 原始數組
R	andom random = new Random();

    public Solution(int[] nums) {
        copyArray = new int[nums.length];
        originalArray = new int[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            copyArray[i] = originalArray[i] = nums[i];
        }
    }
    
    public int[] reset() {
        return originalArray;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < copyArray.length; ++i) {
            int randIndex = getRandIndex(i, copyArray.length);
            // 交換兩個位置數字
            int tmp = copyArray[i];
            copyArray[i] = copyArray[randIndex];
            copyArray[randIndex] = tmp;
        }
        return copyArray;
	}

    int getRandIndex(int min, int max) {// 左閉右開
        // nextInt(n) 傳回值num  0<=num<n 注意右邊開區間
        return random.nextInt(max - min) + min;
    }