随机问题之洗牌算法

instein 发布于2019-08-19 17:13 / 851人阅读

摘要：百度文库洗牌算法提到一种换牌思路随机交换两个位置，共交换次，越大，越接近随机。洗牌插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。每次生成一张最大的牌，与随机的某张牌换位子抽牌抽牌优化换牌插牌插牌优化文章转载自随机问题之洗牌算法

洗牌算法是我们常见的随机问题，在玩游戏、随机排序时经常会碰到。它可以抽象成这样一个问题。

得到一个M以内的所有自然数的随机顺序数组。

在百度搜“洗牌算法”，第一个结果是《百度文库 -- 洗牌算法》。扫了一下里面的内容，很多内容都容易误导别人走上歧途，包括最后用链表代替数组，也只是一个有限的优化（链表也引入了读取效率的损失）。

抽牌思路 基本算法

该文里的第一种方法，可以简单描述成：随机抽牌，放在另一组；再次抽取，抽到空牌则重复抽。
“抽到空牌则重复抽”这会导致后面抽到空牌的机会越来越大，显然是不合理的。可以优化一步成：牌抽走后，原牌变少（而不是留下空牌）。代码如下：

function shuffle_pick_1(m) {
    // 生成m张牌
    var arr = new Array(m);
    for (var i = 0; i < m; i++) {
        arr[i] = i;
    }
    // 每次抽出一张牌，放在另一堆。因为要在数组里抽出元素，把后面的所有元素向前拉一位，所以很耗时
    var arr2 = new Array();
    for (var i = m; i > 0; i--) {
        var rnd = Math.floor(Math.random() * i);
        arr2.push(arr[rnd]);
        arr.splice(rnd, 1);
    }
    return arr2;
}

这个也明显有问题，因为数组如果很大的话，删除中间的某个元素，会导致后面的排队向前走一步，这是一个很耗时的动作。

优化算法

回想一下“我们为什么要删除那个元素？”目的就是为了不产生空牌。除了删除那个元素之外，我们是不是还有其它方式来去除空牌？有的，我们把最后一张未抽的牌放在那个抽走的位置上就可以了。所以，这个思路我们可以优化成这样：

function shuffle_pick(m) {
    // 生成m张牌
    var arr = new Array(m);
    for (var i = 0; i < m; i++) {
        arr[i] = i;
    }

    // 每次抽出一张牌，放在另一堆。把最后一张未抽的牌放在空位子上。
    var arr2 = new Array();
    for (var i = m; i > 0;) {
        var rnd = Math.floor(Math.random() * i);
        arr2.push(arr[rnd]);
        arr[rnd] = arr[--i];
    }
    return arr2;
}

换牌思路

除了抽牌思路，我们还可以用换牌思路。
《百度文库-洗牌算法》提到一种换牌思路：“随机交换两个位置，共交换n次，n越大，越接近随机”。
这个做法是不对的，就算n很大（例如10张牌，进行10次调换），也还存在很大可能“有的牌根本没换位置”。
顺着这个思路，做一点小调整就可以了：第i张与任意一张牌换位子，换完一轮即可。代码如下：

function shuffle_swap(m) {
    // 生成m张牌
    var arr = new Array(m);
    for (var i = 0; i < m; i++) {
        arr[i] = i;
    }

    // 第i张与任意一张牌换位子，换完一轮即可
    for (var i = 0; i < m; i++) {
        var rnd = Math.floor(Math.random() * (i + 1)),
            temp = arr[rnd];
        arr[rnd] = arr[i];
        arr[i] = temp;
    }
    return arr;
}

插牌思路

除了抽牌与换牌的思路，我们还可以用插牌的思路：先有一张牌，第二张牌有两个位置可随机插入（第一张牌前，或后），第三张牌有三个位置可随机插入（放在后面，或插在第一位，或插在第二位），依此类推
代码如下：

function shuffle_insert_1(m) //洗牌 //插牌法
{
    //每次生成一张最大的牌，插在随机的某张牌前。因为要在数组里插入元素，把后面的所有元素向后挤一位，所以很耗时。
    var arr = [0];
    for (var i=1; i
以上的代码也会有一些问题：就是随着牌数的增多，插牌变得越来越困难，因为插牌会导致后面的很多牌都往后推一步。
当然，我们也可以适当的优化一下：先有n-1张牌，第n张牌放在最后，然后与任意一张牌互换位置。
代码如下：
function shuffle_insert(m) //洗牌 //插牌法优化版，可以用数学归纳法证明，这种洗牌是均匀的。
{
    //每次生成一张最大的牌，与随机的某张牌换位子
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i
好的，全部的代码如下，有兴趣的同学可以在自己的机器上试下，看下他们各自的执行效率、以及最后的结果是否是理论随机。



JK：javascript 洗牌算法 









文章转载自《随机问题之--洗牌算法》

GPU云服务器云服务器随机洗牌 java随机洗牌程序 python洗牌算法 webrtc之vad算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/78313.html

也谈前端面试常见问题之『数组乱序』

摘要：看完部分的源码，首先迫不及待想跟大家分享的正是本文主题数组乱序。这是一道经典的前端面试题，给你一个数组，将其打乱，返回新的数组，即为数组乱序，也称为洗牌问题。关于数组乱序，正确的解法应该是，复杂度。前言终于可以开始 Collection Functions 部分了。可能有的童鞋是第一次看楼主的系列文章，这里再做下简单的介绍。楼主在阅读 underscore.js 源码的时候，学到...

tracy 2019-08-19 18:42 评论0 收藏0
Underscore 源码（三）随机洗牌算法

摘要：随机洗牌算法说实话，以前理解数组的排序，都是将数组按照一定的逻辑由大到小或者由小到大排序，我自己是没有碰到过随机打乱数组排序的问题。然后里用的是所谓的洗牌算法，很高效。总结又是三个知识点，分别是随机洗牌分组和函数的实现，没什么复杂的。这是第三篇关于 Underscore 的源码解读，最近一段时间学的东西很少，自己太忙了，一方面忙着找实习，晚上回去还要写毕业论文。毕业论文真的很忧伤，因...

silencezwm 2019-08-20 16:42 评论0 收藏0
数组随机排序：洗牌算法(Fisher–Yates shuffle)

摘要：代码实现代码一测试用例输出其中，代码二测试用例输出其中，参考资料洗牌算法学习笔记数组随机排序洗牌算法给数组随机排序洗牌算法原理原理及步骤 1.定义一个数组（shuffled），长度（length）是原数组（arr）长度2.取 0 到 index (初始0) 随机值 rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...

张金宝 2019-08-20 15:27 评论0 收藏0
洗牌算法

摘要：描述拷贝数组从扫描数组，选择一个随机数新数组的新数组的新数组的原始数组重复第步，直到末尾最终的新数组就是随机的参考三种洗牌算法洗牌算法 Fisher-Yates Shuffle Fisher–Yates 随机置乱算法，通俗说就是生成一个有限集合的随机排列。描述：写下从 1 到 N 的数字取一个从 1 到剩下的数字（包括这个数字）的随机数 k 从低位开始，得到第 k 个还没有被...

omgdog 2019-08-23 17:53 评论0 收藏0
js 数组随机数数组洗牌

摘要：首先通过数组调用是令系统随机选取大于等于且小于的伪随机值进入到函数后分别定义了变量和变量为当前数组的长度，先声明，以便在下面中使用。循环一圈后就形成了对数组的洗牌。这次分享一个随机数组洗牌的一个算法，让你得到随机数组。假如1个数组的值是这样的： const arr = [a, b, c, d, e, f, g]; 因为在实践操作中，在网上搜可以搜到一大堆随机的这些代码。但是实际上究...

jay_tian 2019-08-26 10:30 评论0 收藏0