shuffling / random permutation

又到了野人獻曝的時間了 :)

最近和前輩在聊面試有那些問題可以出
前輩提到一個經典的問題：如何隨機排序一組撲克牌?
換個說法，就是要產生一種52張牌的排列。

前輩提到這個問題可以用排序演算法來解決。
我上維基查了一下，果然在Knuth的大作 The art of computer programming 中有給出兩個演算法 [1]。

假設我們要排序的陣列是 src，大小為N，以 0-based 作為索引方式。
第一個演算法是這樣的:產生另外一個陣列 a，給 a 中的每一個元素一個亂數，接下來對 a 排序，排序的同時將 src 內元素依相同順序移動。排序時可以選用任意的演算法，因此可以在 O(N lg N) 時間內完成。

Knuth 書中的第二個方法更有效率，只需 O(N) 時間即可完成。演算法是: 從 i=N-1 開始依次往前走訪陣列的每個位置，對於每個 i ，產生一個亂數 0<=j<i ，並交換 src[i], src[j]。以 python 來寫的話會像這樣:

for i in range(N-1, 0, -1):
    j = random.randint(0,i)
    src[i], src[j] = src[j], src[i]

有看過這些演算法的朋友會覺得到目前為止都是老調重彈，沒錯，請在往下看。我認為這兩個演算法其實是有關連的，第二個方法可視為第一個方法的特例: 也就是使用 selection sort 來做排序。selection sort 的想法為，每次從未排序的數列中挑出最大(或最小)的一個，將其移到排序完的數列。用簡單的例子來表現:

假設我們要按遞增順序排序這四個數字: 3 2 4 1

第一步是找出最大的數字 4，並放到陣列尾端
3 2 (4) [1] => 3 2 1 | 4

第二步會找到 3，並放到 4 的前面
(3) 2 [1] | 4 => 1 2 | 3 4

接下來會找到 2，順序不變
1 (2) | 3 4 => 1 | 2 3 4

排序完成!

觀察每一步的過程，可分成兩階段，第一階段是找出未排序數列中最大的數字，第二階段是交換到排序數列的開頭。其中第一階段原本要花費 O(n) 的時間以找出最大的值所在的位置，但是既然在第一個演算法中，每個位置的值都是亂數，所以我們可以直接從中隨機挑一個位置當作是最大的數字，這樣有相同的效果，而且時間複雜度只有 O(1)。

好，獻曝完畢 :p

以 selection sort 能夠說明第二個演算法是第一個方法的特例，也許嘗試其他排序法會帶來不同的發現呢。

[1] http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm