random_shuffle原理

random_shuffle，即随机洗牌，算法描述如下：

$$设X_1, X_2, ..., X_t是要洗的t个数的集合。$$

P1.初始化：

$$j = t;$$

P2.生成U：

$$生成在0与1之间一致分布的随机数U；$$

P3.交换：

$$k = \lfloor jU \rfloor + 1, 交换X_j和X_k；$$

P4.减小j：

$$j -= 1。若j > 1，则返回步骤P_2。$$

数学原理其实很简单。第一个被选中的数，概率是1/t，第二个被选中的数的概率是1/(t-1) * (t-1)/t = 1/t，…

这是因为第二个数第一次未被选中，所以是(t-1)/t，而第一次选完之后还剩下t-1个数，所以是1/(t-1)，相乘即可。

于是可以看出，每个数被选到的概率是一样的。

Java代码如下：

for(int i = 0; i < arr.length; i++){
    for(int j = 0; j < arr[i].length; j++){
        int i1 = (int)(Math.random() * arr.length);
        int j1 = (int)(Math.random() * arr[i].length);
        
        int temp = arr[i][j];
        arr[i][j] = arr[i1][j1];
        arr[i1][j1] = temp;
    }
}

PS：很早就知道了随机洗牌是等概率的，而且有时也会用到这个函数，就是忘了具体算法是什么。在网上找了很久都没有找到想要看的东西，最后无意中发现有人说《计算机程序设计艺术》第二卷有它的解释，于是赶紧看了看。概率是我自己推的，的确很简单。在此记录一下。