排列函數

排列和組合是很容易處理的問題。但不知道為什麼，在資訊科系學寫程式之後，排列卻變成相當難的問題。難的地方是在像 C 語言的程式步驟和資料型態上，要考慮很多額外的東西，也遇到很多小麻煩。因此，「取一列資料的全部排列情況」變成一項我一直不會寫程式解決的問題。

而使用像 Haskell 這樣的函數程式語言，將過去所學的知識加以翻覆、折疊，重新整理出一條順暢的思考路線。我最近寫出的排列函數如下；再下去，讓我解釋一下函數構成的想法。

allPermu :: (Eq a) => [a] -> [[a]]
allPermu xs = compact rs
 where rs = map (map (\x -> xs!!x)) (allPermu' [0..((length xs)-1)])

allPermu' :: (Eq a) => [a] -> [[a]]
allPermu' [] = [[]]
allPermu' xs = concat (map f xs)
 where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

compact :: (Eq a) => [a] -> [a]
compact [] = []
compact (x:xs) = if any (x==) xs then compact xs
          else x : compact xs

解析

1. allPermu' 函數：取一列資料的全部排列情況

首先，我覺得取一列資料，如 [4, 3, 4, 5] 的全部排列情況，就是先考慮 4, 3, 4, 5 各數字，將原列資料的這個數字拿掉，求剩下的一列資料的全部排列情況，然後將這個數字都擺在全部排列情況的每一項前面。就這個例子來說， 4, 3, 4, 5 分別要做一次這樣的動作。只考慮 3 ， 3 要和剩下的 [4, 4, 5] 的全部排列組成。 [4, 4, 5] 的全部排列有 [4, 4, 5], [4, 5, 4], [5, 4, 4] ，讓 3 擺在每一項的前面就產生 [3, 4, 4, 5], [3, 4, 5, 4], [3, 5, 4, 4] 這些。

我先要有一個函數是 f = \x -> map (x:) (allPermu' (filter (x/=) [4, 3, 4, 5]) ，是一個函數名為 f ，接到一個參數叫 x ，就把 [4, 3, 4, 5] 中不等於 x 值的項目取出成一列，用一個取全部排列的函數名叫 allPermu' 求少了 x 的全部排列情況。 (只是 allPermu' 在此還沒講它怎麼寫。) 然後，用 map 函數將 (x:) 套到少了 x 的全部排列的每一項前面。這種想法很簡單，對一列資料的每一項，都先把少了那一項的其他資料做排列，所得到的全部排列情況再把少掉的那一項套在前面。

於是，可以說 allPermu' [1, 2] = map f [1, 2] ，再解開就是

map f [1, 2] = [f 1, f 2] = [map (1:) (allPermu' (filter (1/=) [1, 2])),
                         map (2:) (allPermu' (filter (2/=) [1, 2]))]
filter (1/=) [1, 2] = [2]
filter (2/=) [1, 2] = [1]
allPermu' (filter (1/=) [1,2]) = allPermu' [2] --這裡細節省略，我們知道 [2] 全部排列就是 [[2]]
allPermu' (filter (2/=) [1,2]) = allPermu' [1] = [[1]]
map f [1, 2] = [ map (1:) [[2]] , map (2:) [[1]] ]
         = [ [[1, 2]] , [[2, 1]]]

最候出現答案了，但是資料結構的深度加一層。如果把 allPermu' 函數寫成以下這樣......

allPermu' xs = map f xs
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

這是有麻煩的程式。因為當 allPermu' 處理 xs 一次，展開成右邊算式 map f xs 得到的答案會讓資料結構加一層。本來對 [1, 2] 我們想求的答案是 [[1, 2], [2, 1]] ，但是按照前面的計算結果，答案卻是 [[[1, 2]], [[2, 1]]] 。雖然算得出答案，但是表達一列資料的層次越來越深。這時我們需要一個函數讓 [[[1, 2]], [[2, 1]]] 變成 [[1, 2], [2, 1]] ，把資料結構層次降低一層。有一個預設的函數叫 concat 可以做這件事情，如果有一列資料是 [a, b, c, ...] 而 a, b, c, ... 是另外幾列資料， concat [a, b, c, ...] 是把 a, b, c, ... 這幾列資料銜接在一起，於是資料結構的層次減低一層。所以，使用 concat 把 allPermu' 寫得好的程式如下：

allPermu' xs = concat (map f xs)
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

上面這個 allPermu' 是遞迴的情況。而遞迴程式應該要包含遞迴部份和基底部份。把基底和 allPermu' 函數的型態加進去，完整的 allPermu' 函數就是：

allPermu' :: (Eq a) => [a] -> [[a]]
allPermu' [] = [[]]
allPermu' xs = concat (map f xs)
            where f = \x -> map (x:) (allPermu' (filter (x/=) xs))

然而， allPermu' 有個問題是，如果處理的資料列中有重覆資料，因為 filter (x/=) xs 比對 x 值是否相同的作用，會讓 allPermu' [4, 4, 5] 求出不對的答案。即使如此，至少 allPermu' 函數處理一列每個項目都彼此不同的資料是做得對的。後來我想，任何一列可能有重複項目的資料背後都藏了另一列項目彼此不同的資料，就是由原列每一個項目存在的位置編號。例如， [4, 4, 5] 對應到它們的位置編號 [0, 1, 2] 。以下的 allPermu 函數，在處理任何一列資料時，先取出該列資料的一列位置編號，用 allPermu' 函數產生位置編號的全部排列，再將這些排列轉換為原資料。

2. allPermu 函數：產生任何一列資料的全部排列情況

在 Haskell 寫 [0..9] 可以得到 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ，是取得等差遞增序列的特殊語法。對任何一列資料，例如 [4, 3, 4, 5] ，可以寫 [ 0 .. ((length [4, 3, 4, 5]) - 1) ] 產生從 0 開始的遞增序列，也就是 [4, 3, 4, 5] 的位置編號 [0, 1, 2, 3] 。

於是， allPermu' [0..((length [1, 2])-1)] 是 [1, 2] 位置編號的全部排列情況， [[0, 1], [1, 0]] 。接著要將 [[0, 1], [1, 0]] 轉換成 [[1, 2], [2, 1]] 。用 map (\x -> [1,2]!!x) [0, 1] 可以做到這件事情。給一個數字 x ， [1, 2] !! x 就是在 [1, 2] 列中取第 x 個位置的項目。所以，以下的程式可以將 [[0, 1], [1, 0]] 轉換成 [[1, 2], [2, 1]] ：

map (map (\x -> [1, 2]!!x)) [[0, 1], [1, 0]]

第一個 map 將第二個 map 伴隨其參數的段落，即 map (\x -> [1, 2]!!x) ，套到 [[0, 1], [1, 0]] 的每一個項目。接著對 map (\x -> [1, 2]!!x) [0, 1] 來說，是將函數 \x -> [1, 2]!!x 套到 [0, 1] 的每一個項目。所以基本上， allPermu 函數可以寫成：

allPermu xs = rs
           where rs = map (map (\x -> xs!!x)) (allPermu' [0..((length xs)-1)])

但是，考慮 allPermu [4, 3, 4, 5] 會發現出現一些重複的項目，例如，雖然 [0, 1, 2, 3] 和 [2, 1, 0, 3] 的確是兩種不同的排列情況，卻都轉換成 [4, 3, 4, 5] 。於是第三個函數 compact 是將多個重複項目刪掉。 compact 函數在 Haskell 是很普遍的程式處理方式，在此省略其介紹。

3. 結論

本篇由一件以 Haskell 撰寫的全部排列函數，解析一般的處理排列問題的遞迴解題方式。求一列資料的全部排列，是對資料列中的每一項，先求其他項目的全部排列，再將這一項分配結合到其他項目全部排列的每一項之前。透過函數程式語言的寫作方式，可以讓我們重新抓到人們解決問題的直覺能力，使我們從以往局限在程式執行步驟數量的思考方式中得到解脫。