原理:

  1. 有数组A[n],随机数 x 符合0 <= x < n,将A[x]和A[n - 1]对换;
  2. n--,当n>1时重复上述步骤。

代码:

"use strict";

var a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0];

const shuffle = arr => {
    let n = arr.length;
    while (n > 1)
    {
        let x = Math.round(Math.random() * (n - 1));
        if (x != n - 1)
        {
            arr[x] = arr[x] + arr[n - 1];
            arr[n - 1] = arr[x] - arr[n - 1];
            arr[x] = arr[x] - arr[n - 1];
        }
        --n;
    }
    return arr;
};

console.log(shuffle(a));

验证代码:

const MAX = 1000000;

var b = Array(10).fill(0);

for (let i=0;i<MAX;++i)
{
    shuffle(a);
    b = b.map((x, i) => x + a[i]);
}

console.log(b.map(x => x/MAX));

数学归纳法证明:

  1. 假设2个数,那么每个数在每个位置的概率都是1/2;
  2. 假设n个数,那么每个数在最后的位置的概率是1/n,不在的概率是(n-1)/n;
  3. n+1个数的时候,那么每个数在最后的概率是1/(n+1),不在的概率是n/(n+1),假设不在,对于前n个数在前n个数的最后的概率由2知为1/n,即概率是n/(n+1)
  1. 由上可证每个数在每个位置的概率相等为总数分之一.