【青训营】JS洗牌算法
theme: channing-cyan
题目
有几张牌张牌，用js来进行乱序排列，要保持公平性（也就是真的是乱序排列，真的乱！）。
例子1 错误示范
这里用sort方法，用随机数返回，看起来也比较容易理解，大家看看有没有什么问题。
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle(cards) {
return [...cards].sort(() => Math.random() > 0.5 ? -1 : 1);
}
console.log(shuffle(cards));
image.png
其实看这个截图就能看出点有点不一样。我们来测试一下它是否是真的乱。我们让它进行1000000次，让每个值进行相加，如果算法排列是均匀的，说明是真的乱序排列。
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle(cards) {
return [...cards].sort(() => Math.random() > 0.5 ? -1 : 1);
}
const result = Array(10).fill(0);
for(let i = 0; i < 1000000; i++) {
const c = shuffle(cards);
for(let j = 0; j < 10; j++) {
result[j] += c[j];
}
}
console.log(result);
image.png
这里就可以很容易看出来这个例子是不够保证公平性的，排在前列的数值比较小，说明乱的不够充分，如果是抽奖只抽前几名的话就容易导致作者被排在后面的人打。
例子2 正确示范
这里的思路是抽取随机一张牌，放在最后一张牌的后面，再除去当前最后一张牌进行抽取，继续放到最后一张牌的后面。
我们可以通过数学归纳法来验证，如果有一张牌，被抽取的概率为100%/1，如果有俩张牌，被抽取的概率为100%/2，如果有三张牌，被抽取的概率为100%/3 这样递归下去，每张牌都是公平的。
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle(cards) {
const c = [...cards];
for(let i = c.length; i > 0; i--) {
const pIdx = Math.floor(Math.random() * i);
[c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
}
return c;
}
console.log(shuffle(cards));
image.png
我们按照上面的验证方法也验证一下
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function shuffle(cards) {
const c = [...cards];
for(let i = c.length; i > 0; i--) {
const pIdx = Math.floor(Math.random() * i);
[c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
}
return c;
}
console.log(shuffle(cards));
const result = Array(10).fill(0);
for(let i = 0; i < 10000; i++) {
const c = shuffle(cards);
for(let j = 0; j < 10; j++) {
result[j] += c[j];
}
}
console.log(result);
image.png
优化例子2
我们可以用生成器来做，每次抽取其中一张牌，把抽出的牌通过yield方法进行抽出去，做成一个可迭代对象，最后通过...展开操作符进行展开。
const cards = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
function * draw(cards){
const c = [...cards];
for(let i = c.length; i > 0; i--) {
const pIdx = Math.floor(Math.random() * i);
[c[pIdx], c[i - 1]] = [c[i - 1], c[pIdx]];
yield c[i - 1];
}
}
const result = draw(cards);
console.log([...result]);
image.png
总结
写代码应该保证的前提是正确性，如果正确性不能保证的话，那么代码写的再简洁优雅也是徒劳。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-09-18，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录