跳转到内容

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