洗牌算法

如何实现一个完全随机的数组？这并不是一个简单的问题。

通常情况下，我们是这样做的

const random = (min, max) => parseInt(Math.random() * (max - min + 1) + min, 10)
const shuffle = (arr) => {
    for(let i in arr) {
      let rand = random(i, arr.length - 1)
    let temp = arr[i]
    arr[i] = arr[rand]
    arr[rand] = temp
  }
  return arr
}

洗牌算法的正确性原则是：产生的结果比如是有 n! 种可能，否则就是错误的。

常见的错误是

const random = (min, max) => parseInt(Math.random() * (max - min + 1) + min, 10)

const shuffle = (arr) => {
    for(let i in arr) {
      let rand = random(0, arr.length - 1)    // 注意这里
    let temp = arr[i]
    arr[i] = arr[rand]
    arr[rand] = temp
  }
  return arr
}

如果是这样的情况下，产生的结果会有 n ^ n 种可能，而 n^n 不可能等于 n!

我们可以利用蒙特卡罗方法验证一下洗牌算法的正确性

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

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

正确的洗牌算法的结果是

const random = (min, max) => {
  return parseInt(Math.random() * (max - min + 1) + min, 10)
}

const shuffle = (arr) => {
  return arr.map((item, index, array) => {
    const rand = random(index, array.length - 1)
    let temp = item
    item = array[rand]
    array[rand] = temp
    return item
  })
}
const map = new Map()
let n = 1000000
while(n--) {
  const res = shuffle([1,2,3])
  if(map.has(res.toString()))
    map.set(res.toString(), map.get(res.toString()) + 1);
  else map.set(res.toString(), 1)
}

console.log(map);

而错误的洗牌算法的结果是这样的

这样的话，一张牌就会被重复使用，并且生成的概率也不随机