Skip to content

shuffle

Fisher-Yates shuffle

function shuffle(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    const randIdx = Math.floor(Math.random() * (i+1));
    const storedItem = arr[i];
    arr[i] = arr[randIdx];
    arr[randIdx] = storedItem;
  }

  return arr;
}

原理：洗牌，前半部分是原牌，后半部分是已经被 shuffle 过的牌。这种模拟物理手法是基本没问题的。

为什么 Array.sort(Math.random()-0.5)不是 unbias 的？

  • 数学上而言：长度为 n 的数组会有 n! 种排列。而假设是冒泡即比较 c = n(n-1)/2次，每次比较有 2 种结果，一共则有 2^c种排列，和理论上的 n!种排列很难平均对应，所以它一定是不均匀的。
  • 从 Math.random()上的原理而言，js 使用双精度浮点，所以对于 2^c 种 random，x 至少在 63 下才能保证准确的 random()。所以要排序的数组越大，不准确性越高。

ref:

random - Is it correct to use JavaScript Array.sort() method for shuffling? - Stack Overflow

Will It Shuffle?

Fisher–Yates Shuffle