有趣的洗牌演算法

最近因為一些專案,所以需要實做一些撲克牌的洗牌機制。雖然這個動作看起來簡單,但其實對於開發者來說相當有趣,因為真的除了做這種牌類遊戲之外,平常很少用到這樣演算法,也由於有太多種做法,不免著迷於其中。

洗牌目的就是讓結果隨機、不能預期,只不過雖然很多遊戲同樣都是圍繞在亂數產生上面,但撲克牌遊戲(或麻將遊戲)最大的不同,就是同一排組每次發出來的牌,一但發過了就不會再出現一次。這一點,和每次都可以出一到六點數的骰子遊戲,就完全不一樣,不是隨機出一個亂數就可以搞定。

準備工作:先準備個牌組

開始前,先準備四種花色、A 到 K 的牌組,使我們可以以 0 至 51 的號碼去取得任意一張牌。
const suits = [ 'S', 'H', 'D', 'C' ];
const points = [ 'A', 2, 3, 4, 5, 6, 7, 8, 9, 10, 'J', 'Q', 'K' ];
const cards = [];

for (let i = 0; i < 4; i++) {
    for (let j = 0; j < 13; j++) {
        cards.push(points[j] + suits[i]);
    }
}

console.log(cards[10]); // 10S(黑桃10)

方法一:硬幹

最直覺的方法,不外乎就是不斷產生 52 張牌的亂數(0 ~ 51),然後檢查這張牌發過沒,如果牌發過了就重新產生一個新的亂數,持續這個步驟。
let shuffledCards = [];

while(shuffledCards.length != 52) {

    // 取得 0 ~ 51 的亂數
    let idx = Math.floor(Math.random() * 51);
    let card = cards[idx];
    
    // 檢查這張牌是否已經出現過
    if (shuffledCards.indexOf(card) !== -1)
        continue;

    // 沒出現過則放入陣列
    shuffledCards.push(card);
}
雖然這樣的做法可以達成目的,但太不優雅,每次都要去掃一次過往的發牌紀錄,雖然 CPU 很快,這些繁瑣的檢查工作很快能完成,但這對開發者來說,做法太過噁心。

方法二:隨機抽牌

這種方法也是種直覺會想到的方法,隨機把牌從牌組內抽出,使原本牌組的牌越來越少,直到原本的牌組被抽光。簡單來說,就是第一次抽 0 到 51 之間的一張牌,第二次抽 0 到 50 之間的一張牌,以此類推。因為牌越抽越少,我們每次產生出來的亂數範圍就越來越小。
let shuffledCards = [];

for (let left = 51; left >= 0; left--) {

    // 取得 0 至剩餘撲克牌數量之間的亂數
    let idx = Math.floor(Math.random() * left);
    let card = cards[idx];
    
    // 將該張牌從原牌組移除
    cards.splice(idx, 1);
    
    // 放入陣列
    shuffledCards.push(card);
}
這種方法似乎感覺比第一種方法好多了,但一直在破壞原有的牌組陣列,這又不太妥當。對於一個慣 C 來說,乍看下尤為不舒服,因為一般來說,普通陣列是不容許這樣一直變更大小的,記憶體的重配置總是會讓程式效率大幅下降。當然,如果採用的是鏈結(Linked-list)的做法,當然就沒什麼問題,而且這個例子也不是用 C 語言的陣列實作。

方法三:隨機交換

隨機交換的方法,就是幫 0 到 51 位置上的每張牌,隨機選一個排組上的位置進行兩張牌的交換,換言之就是幫每張牌隨機選一個新位置。
// 複製一份牌組陣列
let shuffledCards = Object.assign({}, cards);

for (let i = 0; i < 52; i++) {

    // 隨機取一個位置
    let idx = Math.floor(Math.random() * 51);
    
    // 交換兩張牌
    let temp = shuffledCards[idx];
    shuffledCards[idx] = shuffledCards[i];
    shuffledCards[i] = temp;
}
如果選到了自己怎麼辦?不換位置也是種隨機的結果。

後記

對開發者來說,琢磨這樣的演算法應用,相當有樂趣,可以暫時從工作的苦悶中跳出。追求達成同樣目的,但各種不同做法,有時候其實也是在磨練自己對各種邏輯思維,以及程式技法的掌握度。

留言

這個網誌中的熱門文章

有趣的邏輯問題:是誰在說謊

Web 技術中的 Session 是什麼?

淺談 USB 通訊架構之定義(一)

淺談 USB 通訊架構之定義(二)

Reverse SSH Tunnel 反向打洞實錄