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