Erlang程式設計與問題解決/排列

維基教科書,自由的教學讀本


排列,類似組合,有不可重複的排列和可重複的排列。排列是從一個列表取出指定數目的項目,對取出的相同項目來說,不同的順序代表不同的排列。

排列函數的規格是

permutation ( N , List ) => [ permutation_1, permutation_2, ... ]

在列表 List 中,要取出 N 個,結果得到一列排列情況,每一種排列情況都包含 N 個項目。

不重複的排列[編輯]

從任何列表中取 0 個項目,結果只取得空列表。

permutation(0, _) ->
    [[]];

從空列表中,指定要取任何數目的項目,結果是空集合。

permutation(_, []) ->
    [];

接着是一般情況。要從列表取指定 N 項,做法是將每個項目輪流當做第一筆資料,每一個第一筆資料與其他 N-1 項排列情況結合。在此,列表型示 ( list comprehension ) 可以發揮功用。

permutation(N, Xs) ->
    [ [X|Rs] || X <- Xs,
                Rs <- permutation(N-1, Xs--[X]) ].

測試執行結果:

> test:permutation(3,[a,b,c,d]).
[[a,b,c],
 [a,b,d],
......

> test:permutation(5, [a,b,c]).
[]

> length(test:permutation(3, lists:seq(1,8))).
336

% 從 8 個數字中取 3 個,結果有 336 種組合

可重複的排列[編輯]

可重複的排列是取出每一項之後,又對原列表取剩下的 N-1 項。將上述不重複排列的程式第三句做一點修改,就會得到重複的排列。

permutation(N, Xs) ->
    [ [X|Rs] || X <- Xs,
                Rs <- permutation(N-1, Xs) ].

測試執行結果:

> test:permutation(2,[a,b,c]).
[[a,a],[a,b],[a,c],[b,a],[b,b],[b,c],[c,a],[c,b],[c,c]]

> test:permutation(5, [a,b,c]). 
[[a,a,a,a,a],
 [a,a,a,a,b],
......

> length(test:permutation(3, lists:seq(1,8))).
512

% 從 8 個數字中取 3 個可重複排列,結果有 512 種組合