白板:乱序算法
Liyuk opened this issue · 1 comments
Liyuk commented
描述:任意给你一个数组,请给出一个乱序算法,确保乱序后数组的概率平均。
样例:[1, 2, 3]这个数组,乱序情况有六种123,132,213,231,312,321,这六种情况的平均出现次数均为17%左右。
请实现这个乱序算法,并测试1w次后,每个乱序排列的概率相同。
提示:Fisher–Yates算法
测试代码:
// 冴羽
var times = 100000;
var res = {};
for (var i = 0; i < times; i++) {
var arr = shuffle([1, 2, 3]);
var key = JSON.stringify(arr);
res[key] ? res[key]++ : res[key] = 1;
}
// 为了方便展示,转换成百分比
for (var key in res) {
res[key] = res[key] / times * 100 + '%'
}
console.log(res)
donghaohao commented
function shuffle (arr) {
const l = arr.length
for (let i = l; i > 1; i--) {
const random = Math.floor(Math.random() * i)
if (random === i - 1) {
continue
} else {
let temp = arr[i - 1]
arr[i - 1] = arr[random]
arr[random] = temp
}
}
return arr
}
{ '[3,1,2]': '16.8%',
'[2,1,3]': '16.588%',
'[1,3,2]': '16.518%',
'[2,3,1]': '16.798%',
'[1,2,3]': '16.666%',
'[3,2,1]': '16.63%' }