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