成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

隨機(jī)問題之洗牌算法

instein / 884人閱讀

摘要：百度文庫洗牌算法提到一種換牌思路隨機(jī)交換兩個(gè)位置，共交換次，越大，越接近隨機(jī)。洗牌插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。每次生成一張最大的牌，與隨機(jī)的某張牌換位子抽牌抽牌優(yōu)化換牌插牌插牌優(yōu)化文章轉(zhuǎn)載自隨機(jī)問題之洗牌算法

洗牌算法是我們常見的隨機(jī)問題，在玩游戲、隨機(jī)排序時(shí)經(jīng)常會碰到。它可以抽象成這樣一個(gè)問題。

得到一個(gè)M以內(nèi)的所有自然數(shù)的隨機(jī)順序數(shù)組。

在百度搜“洗牌算法”，第一個(gè)結(jié)果是《百度文庫 -- 洗牌算法》。掃了一下里面的內(nèi)容，很多內(nèi)容都容易誤導(dǎo)別人走上歧途，包括最后用鏈表代替數(shù)組，也只是一個(gè)有限的優(yōu)化（鏈表也引入了讀取效率的損失）。

抽牌思路 基本算法

該文里的第一種方法，可以簡單描述成：隨機(jī)抽牌，放在另一組；再次抽取，抽到空牌則重復(fù)抽。
“抽到空牌則重復(fù)抽”這會導(dǎo)致后面抽到空牌的機(jī)會越來越大，顯然是不合理的?？梢詢?yōu)化一步成：牌抽走后，原牌變少（而不是留下空牌）。代碼如下：

function shuffle_pick_1(m) {
    // 生成m張牌
    var arr = new Array(m);
    for (var i = 0; i < m; i++) {
        arr[i] = i;
    }
    // 每次抽出一張牌，放在另一堆。因?yàn)橐跀?shù)組里抽出元素，把后面的所有元素向前拉一位，所以很耗時(shí)
    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;
}

這個(gè)也明顯有問題，因?yàn)閿?shù)組如果很大的話，刪除中間的某個(gè)元素，會導(dǎo)致后面的排隊(duì)向前走一步，這是一個(gè)很耗時(shí)的動作。

優(yōu)化算法

回想一下“我們?yōu)槭裁匆獎h除那個(gè)元素？”目的就是為了不產(chǎn)生空牌。除了刪除那個(gè)元素之外，我們是不是還有其它方式來去除空牌？有的，我們把最后一張未抽的牌放在那個(gè)抽走的位置上就可以了。所以，這個(gè)思路我們可以優(yōu)化成這樣：

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;
}
換牌思路

除了抽牌思路，我們還可以用換牌思路。
《百度文庫-洗牌算法》提到一種換牌思路：“隨機(jī)交換兩個(gè)位置，共交換n次，n越大，越接近隨機(jī)”。
這個(gè)做法是不對的，就算n很大（例如10張牌，進(jìn)行10次調(diào)換），也還存在很大可能“有的牌根本沒換位置”。
順著這個(gè)思路，做一點(diǎn)小調(diào)整就可以了：第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;
}
插牌思路

除了抽牌與換牌的思路，我們還可以用插牌的思路：先有一張牌，第二張牌有兩個(gè)位置可隨機(jī)插入（第一張牌前，或后），第三張牌有三個(gè)位置可隨機(jī)插入（放在后面，或插在第一位，或插在第二位），依此類推
代碼如下：

function shuffle_insert_1(m) //洗牌 //插牌法
{
    //每次生成一張最大的牌，插在隨機(jī)的某張牌前。因?yàn)橐跀?shù)組里插入元素，把后面的所有元素向后擠一位，所以很耗時(shí)。
    var arr = [0];
    for (var i=1; i

以上的代碼也會有一些問題：就是隨著牌數(shù)的增多，插牌變得越來越困難，因?yàn)椴迮茣?dǎo)致后面的很多牌都往后推一步。


當(dāng)然，我們也可以適當(dāng)?shù)膬?yōu)化一下：先有n-1張牌，第n張牌放在最后，然后與任意一張牌互換位置。
代碼如下：


function shuffle_insert(m) //洗牌 //插牌法優(yōu)化版，可以用數(shù)學(xué)歸納法證明，這種洗牌是均勻的。
{
    //每次生成一張最大的牌，與隨機(jī)的某張牌換位子
    var arr = new Array(m);
    arr[0] = 0;
    for (var i=1; i

好的，全部的代碼如下，有興趣的同學(xué)可以在自己的機(jī)器上試下，看下他們各自的執(zhí)行效率、以及最后的結(jié)果是否是理論隨機(jī)。





JK：javascript 洗牌算法 











文章�(zhuǎn)載自《隨�(jī)問題�--洗牌算法�

文章版權(quán)歸作者所有，未經(jīng)允許請勿�(zhuǎn)�,若此文章存在違規(guī)行為，您可以�(lián)系管理員刪除�

�(zhuǎn)載請注明本文地址：http://systransis.cn/yun/78313.html

相關(guān)文章

  • 也談前端面試常見問題�『數(shù)組亂序�

    摘要：看完部分的源碼，首先迫不及待想跟大家分享的正是本文主題�(shù)組亂序。這是一道經(jīng)典的前端面試�，給你一�(gè)�(shù)�，將其打�，返回新的數(shù)組，即為�(shù)組亂�，也稱為洗牌問題。關(guān)于數(shù)組亂�，正確的解法�(yīng)該是，復(fù)雜度� 前言 終于可以開始 Collection Functions 部分�� 可能有的童鞋是第一次看樓主的系列文�，這里再做下簡單的介紹。樓主在閱讀 underscore.js 源碼的時(shí)候，�(xué)�...

    tracy 評論0 收藏0

  • Underscore 源碼（三�隨機(jī)洗牌算法

    摘要：隨�(jī)洗牌算法說實(shí)�，以前理解數(shù)組的排序，都是將�(shù)組按照一定的邏輯由大到小或者由小到大排�，我自己是沒有碰到過隨機(jī)打亂�(shù)組排序的問題。然后里用的是所謂的洗牌算法，很高效?？偨Y(jié)又是三�(gè)知識�(diǎn)，分別是隨機(jī)洗牌分組和函�(shù)的實(shí)�(xiàn)，沒什么復(fù)雜的� 這是第三篇關(guān)� Underscore 的源碼解讀，最近一段時(shí)間學(xué)的東西很�，自己太忙了，一方面忙著找實(shí)�(xí)，晚上回去還要寫畢業(yè)論文。畢�(yè)論文真的很憂�，因...

    silencezwm 評論0 收藏0

  • �(shù)�隨機(jī)排序�洗牌算法(Fisher–Yates shuffle)

    摘要：代碼實(shí)�(xiàn)代碼一測試用例輸出其中，代碼二測試用例輸出其中，參考資料洗牌算法學(xué)�(xí)筆記�(shù)組隨�(jī)排序洗牌算法給數(shù)組隨�(jī)排序洗牌算法原理 原理及步� 1.定義一�(gè)�(shù)組（shuffled�，長度（length）是原數(shù)組（arr）長�2.� 0 � index (初始0) 隨機(jī)� rand, shuffled[index] = shuffled[rand], shuffled[rand] = arr...

    張金� 評論0 收藏0

  • 洗牌算法

    摘要：描述拷貝數(shù)組從掃描�(shù)組，選擇一�(gè)隨機(jī)�(shù)新數(shù)組的新數(shù)組的新數(shù)組的原始�(shù)組重�(fù)第步，直到末尾最終的新數(shù)組就是隨�(jī)的參考三種洗牌算� 洗牌算法 Fisher-Yates Shuffle Fisher–Yates 隨機(jī)置亂算法，通俗說就是生成一�(gè)有限集合的隨�(jī)排列� 描述� 寫下� 1 � N 的數(shù)� 取一�(gè)� 1 到剩下的�(shù)字（包括這�(gè)�(shù)字）的隨�(jī)�(shù) k 從低位開始，得到� k �(gè)還沒有被...

    omgdog 評論0 收藏0

  • js �(shù)�隨機(jī)�(shù) �(shù)�洗牌

    摘要：首先通過�(shù)組調(diào)用是令系�(tǒng)隨機(jī)選取大于等于且小于的偽隨�(jī)值�(jìn)入到函數(shù)后分別定義了變量和變量為�(dāng)前數(shù)組的長度，先聲明，以便在下面中使用。循�(huán)一圈后就形成了對數(shù)組的洗牌� 這次分享一�(gè)隨機(jī)�(shù)組洗牌的一�(gè)算法，讓你得到隨�(jī)�(shù)�� 假如1�(gè)�(shù)組的值是這樣的： const arr = [a, b, c, d, e, f, g]; �?yàn)樵趯?shí)踐操作中，在�(wǎng)上搜可以搜到一大堆隨機(jī)的這些代碼。但是實(shí)際上�...

    jay_tian 評論0 收藏0

�(fā)表評�

0條評�

instein

�|高級講師

TA的文�

閱讀更多
最新活�
閱讀需要支�1元查�
<