关于算法:洗牌算法

读完本文，你能够去力扣拿下如下题目：

384. 打乱数组

———–

我晓得大家会各种花式排序算法，然而如果叫你打乱一个数组，你是否能做到胸有成竹？即使你拍脑袋想出一个算法，怎么证实你的算法就是正确的呢？乱序算法不像排序算法，后果惟一能够很容易测验，因为「乱」能够有很多种，你怎么能证实你的算法是「真的乱」呢？

所以咱们面临两个问题：

1. 什么叫做「真的乱」？
2. 设计怎么的算法来打乱数组能力做到「真的乱」？

这种算法称为「随机乱置算法」或者「洗牌算法」。

本文分两局部，第一局部详解最罕用的洗牌算法。因为该算法的细节容易出错，且存在好几种变体，虽有轻微差别但都是正确的，所以本文要介绍一种简略的通用思维保障你写出正确的洗牌算法。第二局部解说应用「蒙特卡罗办法」来测验咱们的打乱后果是不是真的乱。蒙特卡罗办法的思维不难，然而实现形式也各有特点的。

一、洗牌算法

此类算法都是靠随机选取元素替换来获取随机性，间接看代码（伪码），该算法有 4 种模式，都是正确的：

// 失去一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

// 第一种写法
void shuffle(int[] arr) {int n = arr.length();
    /******** 区别只有这两行 ********/
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最初随机选一个元素
        int rand = randInt(i, n - 1);
        /*************************/
        swap(arr[i], arr[rand]);
    }
}

// 第二种写法
    for (int i = 0 ; i < n - 1; i++)
        int rand = randInt(i, n - 1);

// 第三种写法
    for (int i = n - 1 ; i >= 0; i--)
        int rand = randInt(0, i);

// 第四种写法
    for (int i = n - 1 ; i > 0; i--)
        int rand = randInt(0, i);

剖析洗牌算法正确性的准则：产生的后果必须有 n! 种可能，否则就是谬误的。这个很好解释，因为一个长度为 n 的数组的全排列就有 n! 种，也就是说打乱后果总共有 n! 种。算法必须可能反映这个事实，才是正确的。

咱们先用这个准则剖析一下 第一种写法 的正确性：

// 假如传入这样一个 arr
int[] arr = {1,3,5,7,9};

void shuffle(int[] arr) {int n = arr.length(); // 5
    for (int i = 0 ; i < n; i++) {int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

for 循环第一轮迭代时，i = 0，rand 的取值范畴是 [0, 4]，有 5 个可能的取值。

for 循环第二轮迭代时，i = 1，rand 的取值范畴是 [1, 4]，有 4 个可能的取值。

前面以此类推，直到最初一次迭代，i = 4，rand 的取值范畴是 [4, 4]，只有 1 个可能的取值。

能够看到，整个过程产生的所有可能后果有 n! = 5! = 5*4*3*2*1 种，所以这个算法是正确的。

剖析 第二种写法，后面的迭代都是一样的，少了一次迭代而已。所以最初一次迭代时 i = 3，rand 的取值范畴是 [3, 4]，有 2 个可能的取值。

// 第二种写法
// arr = {1,3,5,7,9}, n = 5
    for (int i = 0 ; i < n - 1; i++)
        int rand = randInt(i, n - 1);

所以整个过程产生的所有可能后果依然有 5*4*3*2 = 5! = n! 种，因为乘以 1 可有可无嘛。所以这种写法也是正确的。

如果以上内容你都能了解，那么你就能发现 第三种写法 就是第一种写法，只是将数组从后往前迭代而已；第四种写法 是第二种写法从后往前来。所以它们都是正确的。

如果读者思考过洗牌算法，可能会想出如下的算法，然而 这种写法是谬误的：

void shuffle(int[] arr) {int n = arr.length();
    for (int i = 0 ; i < n; i++) {// 每次都从闭区间 [0, n-1]
        // 中随机选取元素进行替换
        int rand = randInt(0, n - 1);
        swap(arr[i], arr[rand]);
    }
}

当初你应该明确这种写法为什么会谬误了。因为这种写法失去的所有可能后果有 n^n 种，而不是 n! 种，而且 n^n 不可能是 n! 的整数倍。

比如说 arr = {1,2,3}，正确的后果应该有 3!= 6 种可能，而这种写法总共有 3^3 = 27 种可能后果。因为 27 不能被 6 整除，所以肯定有某些状况被「偏袒」了，也就是说某些状况呈现的概率会大一些，所以这种打乱后果不算「真的乱」。

下面咱们从直觉上简略解释了洗牌算法正确的准则，没有数学证实，我想大家也懒得证实。对于概率问题咱们能够应用「蒙特卡罗办法」进行简略验证。

二、蒙特卡罗办法验证正确性

洗牌算法，或者说随机乱置算法的 正确性衡量标准是：对于每种可能的后果呈现的概率必须相等，也就是说要足够随机。

如果不必数学严格证实概率相等，能够用蒙特卡罗办法近似地预计出概率是否相等，后果是否足够随机。

记得高中有道数学题：往一个正方形外面随机打点，这个正方形里紧贴着一个圆，通知你打点的总数和落在圆里的点的数量，让你计算圆周率。

这其实就是利用了蒙特卡罗办法：当打的点足够多的时候，点的数量就能够近似代表图形的面积。通过面积公式，由正方形和圆的面积比值是能够很容易推出圆周率的。当然打的点越多，算出的圆周率越精确，充分体现了鼎力出奇观的真谛。

相似的，咱们能够对同一个数组进行一百万次洗牌，统计各种后果呈现的次数，把频率作为概率，能够很容易看出洗牌算法是否正确。整体思维很简略，不过实现起来也有些技巧的，上面简略剖析几种实现思路。

第一种思路，咱们把数组 arr 的所有排列组合都列举进去，做成一个直方图（假如 arr = {1,2,3}）：

每次进行洗牌算法后，就把失去的打乱后果对应的频数加一，反复进行 100 万次，如果每种后果呈现的总次数差不多，那就阐明每种后果呈现的概率应该是相等的。写一下这个思路的伪代码：

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 + " "); // 频率

这种测验计划是可行的，不过可能有读者会问，arr 的全副排列有 n! 种（n 为 arr 的长度），如果 n 比拟大，那岂不是空间复杂度爆炸了？

是的，不过作为一种验证办法，咱们不须要 n 太大，个别用长度为 5 或 6 的 arr 试下就差不多了吧，因为咱们只想比拟概率验证一下正确性而已。

第二种思路，能够这样想，arr 数组中全都是 0，只有一个 1。咱们对 arr 进行 100 万次打乱，记录每个索引地位呈现 1 的次数，如果每个索引呈现的次数差不多，也能够阐明每种打乱后果的概率是相等的。

void shuffle(int[] arr);

// 蒙特卡罗办法
int N = 1000000;    
int[] arr = {1,0,0,0,0};
int[] count = new int[arr.length];
for (int i = 0; i < N; i++) {shuffle(arr); // 打乱 arr
    for (int j = 0; j < arr.length; j++) 
        if (arr[j] == 1) {count[j]++;
            break;
        }
}
for (int feq : count) 
    print(feq / N + " "); // 频率

这种思路也是可行的，而且防止了阶乘级的空间复杂度，然而多了嵌套 for 循环，工夫复杂度高一点。不过因为咱们的测试数据量不会有多大，这些问题都能够疏忽。

另外，仔细的读者可能发现一个问题，上述两种思路申明 arr 的地位不同，一个在 for 循环里，一个在 for 循环之外。其实成果都是一样的，因为咱们的算法总要打乱 arr，所以 arr 的程序并不重要，只有元素不变就行。

三、最初总结

本文第一局部介绍了洗牌算法（随机乱置算法），通过一个简略的剖析技巧证实了该算法的四种正确模式，并且剖析了一种常见的谬误写法，置信你肯定可能写出正确的洗牌算法了。

第二局部写了洗牌算法正确性的衡量标准，即每种随机后果呈现的概率必须相等。如果咱们不必严格的数学证实，能够通过蒙特卡罗办法鼎力出奇观，粗略验证算法的正确性。蒙特卡罗办法也有不同的思路，不过要求不用太严格，因为咱们只是寻求一个简略的验证。