2015年4月29日 星期三

演算法訓練 7 ─ 撲克牌對切洗牌 (Dovetail Shuffle)

http://4rdp.blogspot.com/2015/04/7-dovetail-shuffle.html

圖片來源 維基百科洗牌條目
中小學時,我喜歡做棋玩棋,專科及大學學生時代,除了玩電腦外,也很喜歡玩橋牌,收藏三十餘本絕版橋書,亦有取得初級橋士證,不過結婚後就沒再玩了,應該退休後才會再重拾這份嗜好吧。

回歸正傳,試寫一程式執行對切洗牌 (Riffle or Dovetail Shuffle)。




這裡所出的題目,不限制程式語言,甚至以純文字表述也歡迎,就算有人已經以某種語言發表答案,也歡迎你用更精簡方式或是其它程式語言再重製,一個好的程式,應同時注重程式碼大小、占用記憶體資源與執行效率。在此貼出的程式碼,著作權除非另有聲明,否則屬貼文者的,其內容純研究討論供大眾參考,也不負任何使用損壞賠償責任。

9 則留言:

  1. 回覆
    1. 薛老師過譽了,年少時沉迷於遊戲,不過也從其中體悟一些哲理,現在很多傳統活動已經式微,被許多電子遊戲取代,橋牌是其中一例,改日貼一篇我對合約橋牌的感想,歡迎老師一同分享年輕時好玩的活動。

      刪除
  2. card[52]
    left[26]=card[0-25]
    right[26]=card[26-51]
    shuffled[52]
    for(int i=0;i<26;i++){
    shuffled[i*2]=left[i]
    shuffled[i*2+1]=right[i]
    }

    回覆刪除
    回覆
    1. Peter,
      謝謝你提供程式範例,這個是非常均勻的洗牌。

      刪除
  3. 關於 Peter 的演算法,有點建議。
    假設有個陣列,為方便解釋,只使用長度=10個元素。
    A[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }
    經過一次程式,跑出來的結果為 { 0, 5, 1, 6, 2, 7, 3, 8, 4, 9}
    原A[10] 陣列,重跑一次的結果還是為 { 0, 5, 1, 6, 2, 7, 3, 8, 4, 9}

    如果 A 陣列經過原程式遞迴跑10次出來的結果,與第二次再用A陣列,在經過原程式重新遞迴10出來的結果會一樣。
    這樣就 "有跡可循" 變成不是隨機、真正亂數的過程了。

    我的建議是,在 for 這迴圈內加入一個隨機的種子。
    隨機產生0或1

    if rand() = 0
    shuffled[0] = left [0]
    else shuffle[0] = right[0]

    這樣類似的作法。

    回覆刪除
    回覆
    1. 這樣子就會類似人對切洗牌時,左手的排壓掉下去好幾張了,右手的牌才掉一張、這樣類似過程。

      刪除
    2. 我想起來了,任何「規律的洗牌」洗一洗幾回合之後,都會回復原來牌組次序,
      請參考尋找自己的數列一文 http://4rdp.blogspot.tw/2013/07/oeis-a227392-1-2-2-3-5-6-10-6-9.html
      因此加入隨機因子,可確保不會發生重複狀況

      刪除
  4. 高中第一個程式語言vb,老師示範的一道題目,我印象深刻
    用0~51陣列代表52張牌,然後用亂數取任兩張牌作交換的動作
    交換的動作重覆幾次之後,即可以有洗牌的感覺

    回覆刪除
    回覆
    1. Scott 您好,

      歡迎您經常留言,這確實是不錯的洗牌法,不過次數要夠多,才洗得乾淨。

      刪除