原理:
- 有数组A[n],随机数 x 符合0 <= x < n,将A[x]和A[n - 1]对换;
- 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));
数学归纳法证明:
- 假设2个数,那么每个数在每个位置的概率都是1/2;
- 假设n个数,那么每个数在最后的位置的概率是1/n,不在的概率是(n-1)/n;
- n+1个数的时候,那么每个数在最后的概率是1/(n+1),不在的概率是n/(n+1),假设不在,对于前n个数在前n个数的最后的概率由2知为1/n,即概率是n/(n+1)
- 1/n = 1/(n+1);
- 由上可证每个数在每个位置的概率相等为总数分之一.