扫雷与算法：如何随机化的布雷（二）之洗牌算法

柔情只为你懂 2022-01-21 07:55 487阅读 0赞

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

前言：[扫雷与算法：如何随机化的布雷（一）][Link 1]

先来思考一个问题：**有一个大小为 100 的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 1 个数？**

最简单的方法是利用系统的方法 `Math.random() * 100` ，这样就可以拿到一个 0 到 99 的随机数，然后去数组找对应的位置就即可。

接下来在思考一个问题： **有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 50 个数？**

**注意数字不能重复！**

如果根据上面的思路，你第一想法是：随机 50 次不就行了？

但是，这样做有个很明显的 bug ：数字是会重复的。

修改一下？

弄一个数组，把每一次随机的数都放到数组里，下一次随机就看这个数组里面有没有这数，有的话就继续随机，直到这个数组里面有 50 个数字就停止。

这样是可以的！

但，还是有个小问题，考虑一下极端情况：**有一个大小为100的数组，里面的元素是从 1 到 100 按顺序排列，怎样随机的从里面选择 99 个数**。

如果按照上面的方法操作，越往后选择的数字跟前面已经挑选的数字重复的概率越高，这就会造成如果数组很大，选择的数字数目也很大的话，重复次数在量级上会很大。

这个时候就需要换一个思路，如果先将数组里面的元素**打乱**，那么按顺序选择前 50 个不就可以了？

是的！

但我们得注意什么叫乱？

一副扑克有 54 张牌，有 54! 种排列方式。所谓的打乱指的是，你所执行的操作，应该能够 **等概率地生成** 这 54! 种结果中的一种。

洗牌算法就能做到这一点。

### 洗牌算法 ###

**Fisher–Yates shuffle** 算法由 Ronald Fisher 和 Frank Yates 于 1938 年提出，在 1964 年由 Richard Durstenfeld 改编为适用于电脑编程的版本。

这个算法很牛逼却很好理解，通俗的解释就是：将最后一个数和前面任意 n-1 个数中的一个数进行交换，然后倒数第二个数和前面任意 n-2 个数中的一个数进行交换。。。

![640?wx\_fmt=gif][640_wx_fmt_gif]

### 小程序实现代码 ###

for (var i = this.rowCount * this.colCount - 1; i >= 0 ; i--){  var iX = parseInt(i / this.colCount);  var iY = i % this.colCount;  var randNumber = this.rangeRandom(0, i + 1);  var randX = parseInt(randNumber / this.colCount);  var randY = randNumber % this.colCount; //交换两个位置  var temp = tmpMineMap[iX][iY];  tmpMineMap[iX][iY] = tmpMineMap[randX][randY];  tmpMineMap[randX][randY] = temp;}var i = this.rowCount * this.colCount - 1; i >= 0 ; i--){
        
      var iX = parseInt(i / this.colCount);
      var iY = i % this.colCount;
    
      var randNumber = this.rangeRandom(0, i + 1);
    
      var randX = parseInt(randNumber / this.colCount);
      var randY = randNumber % this.colCount;
    
     //交换两个位置
      var temp = tmpMineMap[iX][iY];
      tmpMineMap[iX][iY] = tmpMineMap[randX][randY];
      tmpMineMap[randX][randY] = temp;
    }

### 小程序实现效果 ###

![640?wx\_fmt=gif][640_wx_fmt_gif 1]

![640?wx\_fmt=png][640_wx_fmt_png]

[640_wx_fmt_jpeg]: /images/20220121/0836194eca6f4452a329bb4d8ad0846a.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485477&idx=1&sn=37f942e0bbc821d9592972118cddedfe&chksm=fa0e67a4cd79eeb2aefe1b9b1877d9a92a9decd8b5e442a91b0c38a4df319cb7940ab4cb09e1&scene=21#wechat_redirect
[640_wx_fmt_gif]: /images/20220121/791ea9db345d486a99bcd71245977a85.png
[640_wx_fmt_gif 1]: /images/20220121/52d71f3097af41c1a7470fa6ceefcbcc.png
[640_wx_fmt_png]: /images/20220121/041d27ce76744237be9964549bfd91f0.png