Javascript

JS洗牌算法

本文主要是介绍JS洗牌算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

有几张牌张牌,用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));

https://img1.sycdn.imooc.com/61483ca00001746204850433.jpg

其实看这个截图就能看出点有点不一样。我们来测试一下它是否是真的乱。我们让它进行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);


https://img1.sycdn.imooc.com/61483cec00010fee09020561.jpg 这里就可以很容易看出来这个例子是不够保证公平性的,排在前列的数值比较小,说明乱的不够充分,如果是抽奖只抽前几名的话就容易导致作者被排在后面的人打。

例子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));

https://img1.sycdn.imooc.com/61483ced0001090105330513.jpg 

我们按照上面的验证方法也验证一下

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);

https://img4.sycdn.imooc.com/61483d210001e9df09240425.jpg

优化例子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]);

https://img3.sycdn.imooc.com/61483d3c0001a7a905900490.jpg

总结

写代码应该保证的前提是正确性,如果正确性不能保证的话,那么代码写的再简洁优雅也是徒劳。


作者:大熊G
链接:https://juejin.cn/post/7009293935218524167
来源:掘金
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


这篇关于JS洗牌算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!