Javascript随机排列数组-要求概率一样

今天做了一道很有意思的题。如何在Js中实现一个随机排列数组的算法，要求排列之后每一次组合出现的概率相同。完整题目如下：

et arr = [1, 2, 3];

shuffle(arr);
// arr = [3, 2, 1]

shuffle(arr);
// arr = [2, 1, 3]

shuffle(arr);
// arr = [3, 1, 2]
//所有元素顺序应该具有相等的概率。例如，可以将 [1,2,3] 重新排序为 [1,2,3] 或 [1,3,2] 或 [3,1,2] 等，每种情况的概率相等。

可能我们第一反应就是使用Math.random

function shuffle(array) {
  array.sort(() => Math.random() - 0.5);
}

但是这个测试一下，就会发现，概率并不是平均的。
测试代码如下：

// 所有可能排列的出现次数
let count = {
  '123': 0,
  '132': 0,
  '213': 0,
  '231': 0,
  '321': 0,
  '312': 0
};

for (let i = 0; i < 1000000; i++) {
  let array = [1, 2, 3];
  shuffle(array);
  count[array.join('')]++;
}

// 显示所有可能排列的出现次数
for (let key in count) {
  alert(`${key}: ${count[key]}`);
}

结果如下：（取决于JavaScript引擎）

123: 250706
132: 124425
213: 249618
231: 124880
312: 125148
321: 125223

这里有一个很有意思的算法，能够很好的保证平均概率随机，它就是 Fisher-Yates shuffle，其思路是：逆向遍历数组，并将每个元素与其前面的随机的一个元素互换位置，代码如下：

function shuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    let j = Math.floor(Math.random() * (i + 1)); // 从 0 到 i 的随机索引

    // 交换元素 array[i] 和 array[j]
    // 我们使用“解构分配（destructuring assignment）”语法来实现它
    // 可以写成：
    // let t = array[i]; array[i] = array[j]; array[j] = t
    [array[i], array[j]] = [array[j], array[i]];
  }
}

测试结果如下：

123: 166693
132: 166647
213: 166628
231: 167517
312: 166199
321: 166316