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

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

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

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

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

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

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

总结

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

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