Fisher–Yates shuffle
2022/4/24
關於洗牌這件事又得從研究所時期說起了,因為我當時是開發蜜月橋牌 AI,需要有洗牌發牌這件事,當時也是被彥吉大神上了一課,吉神就像是我的第二個指導教授一樣,感恩吉神讚嘆吉神。
Shuffle an Array
說是洗牌其實也可以想成要打亂一個array
,洗牌只是其中一個應用場景,只說洗牌可能會讓人誤會,因為現實世界中洗牌的方式有很多種,比如我們很常見到的交疊洗牌 Riffle Shuffle。
上面這個就是交疊洗牌。
剛好最近翻到 2016 的照片就順手貼上來 XDD,當時與魔術社的好友德偉一起在整理一些紙牌技巧,心血來潮就幫他拍了一些照片,當時真的是很瘦阿,髮型也很潮,歲月真的是一把殺豬刀。
剛好在 leetcode 中也有一題1470. Shuffle the Array是類似這種交疊洗牌的,只是他要完美的一張一張分開交疊,這種完美的交疊洗牌叫做Faro Shuffle,中文好像通常稱為完美洗牌或是鴿尾式洗牌,這種洗牌蠻酷的可以做到很多事情,比如我知道只要連做 Faro shuffle 8 次,整副牌的順序就會恢復原狀,但好像根據 out、in(本來第一張牌在上還在下)的洗法也會有差異的樣子,好像混合洗最快6 次就可以還原,我也是點了wiki的資料進去看到介紹才知道的,應該很多人以前在學 Faro 的時候都只知道 8 次吧,難道是我已知用火?!
有學過的可以留言告訴我,你們一開始就知道是 6 次還是跟我一樣聽到 8 次。更正一下,這邊 6 次是要剛剛好 64 張牌才可以,52 張的話還是要 8 次才可以,是我沒看清楚 XD,感謝魔術圈的仲神與不認識的大神們提醒,在此修正。
2022/7/18
那我這邊要探討的不是現實中的洗牌,而是 leetcode 的384. Shuffle an Array,對的沒錯,剛好 leetcode 都有,我比較意外的是這題居然被歸類為 medium 的題目。
簡單說就是要公平的打亂,造成每種組合的機率要相等。
比如丟骰子,丟兩顆骰子會出現 2~12 點共 11 種可能,但造成這些可能的機率並不一樣,比如點數 7 應該是比較容易出現的,能造成 7 點的組合有 2 跟 5、1 跟 6、3 跟 4,但是能造成 12 點的就只有兩個 6 了,機率明顯比較小,所以如果是要打亂骰子就不是一個公平的打亂。
實作
直覺的做法
多宣告一個 array,然後將原來 array 裡的值隨機一個一個 push 到新 array 中,這是我最直覺想到的做法,應該也是很多人的第一感。
function shuffle(deck) {
const newDeck = [];
while (deck.length > 0) {
const r = Math.floor(Math.random() * deck.length);
const card = deck.splice(r, 1);
newDeck.push(...card);
}
return newDeck;
}
其實這麼做也沒問題,就是效率差了點,因為 array 的 delete 為
直覺的優化做法
想法大致上就是從第一張牌開始,隨機的跟其他張牌交換,這樣一直換到最後一張牌,這些操作都在同個 array 中完成,所以就能將時間複雜度優化到
function shuffleX(deck) {
for (let i = 0; i < deck.length; i++) {
const r = Math.floor(Math.random() * deck.length);
[deck[i], deck[r]] = [deck[r], deck[i]];
}
}
[deck[i], deck[r]] = [deck[r], deck[i]]
這段就只是交換他們的值,算是 js 很方便的語法,其他語言寫起來應該是要像下面這樣,多宣告一個變數作為暫存。
temp = deck[i]
deck[i] = deck[r]
deck[r] = temp
然而這段看似簡單的想法其實是會有問題的,可以先自己想想看問題是什麼,再往下看分析。
Fisher-Yates Shuffle
我就先直接放上本篇主題Fisher-Yates Shuffle,讓大家可以想一下這兩個做法的差別。
其實想法也是很簡單,就是交換過的就不再換了,比如第一張牌可以跟 52 張牌換,換完後第一張牌就固定了,到第二張牌只能跟後面 51 張牌換,第三張牌只能跟 50 張換,依此類推,最後一張牌就不用換了,因為也只能跟自己換。
實作上我是從後面換回來,這樣只要讓 random number 的範圍每次都-1 就好,當然你想要從前面開始也可以。
function shuffle(deck) {
for (let i = deck.length - 1; i > 0; i--) {
const r = Math.floor(Math.random() * (i + 1));
[deck[i], deck[r]] = [deck[r], deck[i]];
}
}
分析
那上面兩種方法到底會有什麼影響呢?
那就是造成的結果不公平,機率不平均的問題!
實際給數字來實驗看看吧,數學超差的我最喜歡帶數字進去算了,當然還有最純粹的暴力解!
給定一個初始值為 1,2,3 的 arraydeck
const deck = [1, 2, 3];
正常打亂 123 的結果可能有 3 x 2 x 1 = 3! = 6 種可能,分別為 123、132、213、231、321、312。
但是用我們上面的方法來做的話,可能的換法為
暴力展開
舉個例子:
給一個初始為 123 的 array,使用較差的做法出來後分佈如下圖
第一次換有三種換法
- index1 跟 index1 換 --> 123
- index1 跟 index2 換 --> 213
- index1 跟 index3 換 --> 321
(為了方便理解我這邊 index 從 1 開始算)
第二次換
拿 123 的分支當範例
- index2 跟 index1 換 --> 213
- index2 跟 index2 換 --> 123
- index2 跟 index3 換 --> 132
213 的分支
- index2 跟 index1 換 --> 123
- index2 跟 index2 換 --> 213
- index2 跟 index3 換 --> 231
依此類推如下圖
第三次換
(這邊因為整棵樹會太大,我把根節點拿掉且拆成三顆子樹來看)
全部列出來後可以看到能造成 123、321、312 的換法有 4 種,而能造成 132、213、231 的換法則有 5 種。
通過不同的交換方式卻能產生相同的結果,但造成的各種結果機率並不一樣。
程式驗證
數字小的時候可能還會以為是機率問題而沒有感覺,那我們就直接讓他跑 60 萬次看看結果,如果機率是相同的那應該會每種可能都差不多出現 10 萬次。
const count = { 123: 0, 132: 0, 213: 0, 231: 0, 312: 0, 321: 0 };
for (let i = 0; i < 600000; i++) {
const deck = [1, 2, 3];
shuffleX(deck);
count[deck.join('')]++;
}
console.log(count);
再來看看使用 Fisher-Yates Shuffle 後的結果
4 張牌的時候差距就更明顯了,這邊洗了 240 萬次,一樣理論上每種可能都會出現差不多 10 萬次。
可以看到明顯機率不平均
心得
其實我自己是不會犯本文中的錯誤的,不是因為我多厲害,是我當時把功能做出來之後根本不會去優化,能動就好,優化是什麼?能吃嗎?
不優化就不會犯錯 XDD,所以我感覺這個錯誤應該是夠厲害的人才會犯的錯,總之還是學習了。
當時是因為我的發牌實在寫得很搞笑讓彥吉看不下去了,叫我去查查,才知道這個洗牌的,後來在做平台的時候也用上了,在記錄這篇的時候還查到了 faro shuffle 的冷知識,有種無用的知識增加了的感覺。
Reference
JavaScript 學演算法(二十一)- 洗牌演算法
The Danger of Naïveté
新登場人物
彥吉大神:
我研究所時的學長,之前沒詳細介紹過吉神,簡單說就是神,不是學霸而是神,學霸年年有,但是神是久久才會出現一次的,碩士兩年不曉得寫了幾篇論文,都數不清他出國發表幾次了,而且各種得獎,當年也受到彥吉大神很多的幫忙是個非常照顧人的學長,甚至連出社會開始工作了我還是一直找吉神幫忙,感恩彥吉讚嘆彥吉!
德偉:
大學時期魔術社的好夥伴,攝影師、3D 動畫師,是個非常有喜感的人,感覺他的人生就是在變胖與瘦回來之間無限循環,只要一年不見就會發現他完全變了個人,厲害的是他都還能瘦得回來。