Erlang程式設計與問題解決/組合

計算機科學 > 編程 > Erlang程式設計與問題解決

關於組合，用 Erlang 可以很簡單地處理。首先要注意，組合問題是給一個列表，並且要指定取多少數目的項目做組合。組合的結果是多種組合情況。所以，組合程式的規格是

combination(N, List) => [combination_1, combination_2, ... ]

讓我們開始寫第一句。

combination(0, _list) ->
    [[]];

任何列表取 0 個項目，結果只有一種組合： [] 。

那麼，從空列表中取出任何項目的組合呢？

combination(_num, []) ->
    [];

結果就是空集合。

以上二項組合的基本部份定義好，接下來有二方面的考量：不重複的組合，以及可重複的組合。

不重複的組合

不重複的組合，就像是從一副牌中取指定的張數。基本特性就是不會重覆。

先考慮其中一種簡單情況，從長度為 N 的列表中，取出 N 個項目：

combination(N, Xs) when N >= length(Xs) ->
    [Xs];

至於其他情況，結果若不是在先取走任何一張情況下、用同樣的方法取其他張，就是對同樣的任何一張牌不要取走它的情況下、用同樣的方法從其他牌取原定的張數。

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

實際檢測一下，在 52 張牌中取 5 張：

> length(test:combination(5, lists:seq(1,52))).
2598960

然而效能消耗方面，有一些問題，考慮以下的執行：

> [ test:combination(N, lists:seq(1,81)) || N <- lists:seq(1,81) ].

執行過程非常久。

可重複的組合

可重複的組合，結果是可能在先取走任何一項的情況下，將取出的物品放回去，再用同樣的方法做一次，直到抽取的數目足夠了。或者可能是，在抽不到某一項物品的情況下，將其他物品抽取指定的次數。

由以上，不重複的組合的函數，只要改一些小地方，就形成可重複的組合：

% combination(N, Xs) when N >= length(Xs) ->
%     [Xs];
combination(N, [X|Xs]) ->
    [ [X|Rs] || Rs <- combination(N-1, [X|Xs]) ]
    ++ combination(N, Xs).

測試一下，在 10 種批薩中點其中 3 種：

> length(test:combination(3, lists:seq(1,10))).
220