Random shuffling

Doing the Microsoft Shuffle: Algorithm Fail in Browser Ballot; Rob Weir: An Antic Disposition

這是我近日看過的一篇有趣文章。話說歐盟控告微軟的 IE 造成壟斷，雙方後來和解，同意於新版本的 Windows 之中加入選單畫面，讓用家選擇安裝喜歡的瀏覽器（見下圖）。選單中五種瀏覽器的位置，是隨機決定的，不過上述網誌的作者卻發現，五種瀏覽器的位置，實在稱不上是均勻分佈 (uniformly distributed)。後來他深入研究微軟「兜亂」(shuffle) 五個位置所用的程式碼，發現結果相當不平均。

要兜亂一個序列，或者用數學化一點的語言來說，要生成一個隨機置換（這裏「隨機」的意思當然不是照字面解，而是照一般人的用法去解，也就是不止隨機，還要均勻分佈），最方便穩妥的辦法當然是 Fisher-Yates shuffle。用一行 pseudocode去講，就是

p = {1, 2, 3, 4, 5}; for (i=n; i>1; --i) swap(p[i], p[rand(i)])

微軟捨此不用，反而做類似以下的事情：

p = {1, 2, 3, 4, 5}; sort(p, RandomSort)

當然，p 並非隨機序列，按其內容排序，並不會得出隨機結果，所以微軟排序時，用了以下的隨機「比較函數」(comparator)：

function RandomSort (a,b) {return (0.5 - Math.random());}

換句話題，當你為兩個數目 a 與 b 排大小時，程式所看的並非 a 的數值是否真的小於 b，而是隨機產生一個介乎 -0.5 與 +0.5 之間的數字 x = 0.5 - Math.random()，若 x 是負數，便扮作 a<b；若是正數，則扮作a>b；若 x=0，則當 a=b。

利用這樣的隨機比較函數，當然也會得出隨機置換，只不過置換的分佈既不夠平均，亦因排序方法而異。其實腦筋清楚並對中學的統計學稍為有點認識的人，根本都不會犯上這種錯誤，所以前述文章令我喜歡的地方，並不是它有甚麼令人意外的發現或結論，而是作者竟然肯花那麼多時間去找出實際錯誤的來源。這種探究精神，才真的令我佩服。

該網誌的留言亦非常值得一看。例如 #27 的 Tom 問，若將 Fisher-Yates shuffle 改動成 for (i=1; i<=n; ++i) swap(p[i], p[rand(n)])，為甚麼不算均勻置換？#31 的 Dave 就回答得相當精闢。Tom 另外提及 for (i=1; i<=n; ++i) swap(p[rand(n)], p[rand(n)])，其問題所在也是有趣的思考材料甚至面試題目。（有無讀者可以用簡單的方法指出問題所在？）留言 #52 及 #53 則反映原來人們對統計學的認識，可以相當出人意表。留言 #92 則指出原來微軟所用的蠢方法，一個有名的 Javascript 教學網站亦有教！至於留言 #95 的 Issac 君，與文章作者同樣具探索精神。他發現用微軟所用的隨機比較法，五個位置的置換結果於不同的排序方法之下，差異可以頗為巨大。詳見：

Randomizing by Random-Comparison Sorting (Revisited); 2718.us blog