开发者

create a list from a list of lists

I need to do the following: given a list of lists I need to find all possible combinations of the lists such that if some of these lists belong in such a combination, then they have no elements in common and the list created by appending the lists in the combination has a given length. Any ideas?

Example:

Say P= [[1,2,3],[4,5,6],[2,5],[7,9],[7,10],[8],[10]]. 

N a given number, say N=10. I need to search through P in order to find appropriate lists, with no elements in common, and add them in a list L such that the lengt开发者_StackOverflowh of the union of L is 10. So in the above example :

L=[[1,2,3],[4,5,6],[7,9],[8],[10]]. It might be very easy but I'm new in Prolog


Given nobody's answered, and it's been quite a while since I've written anything in Prolog and I figured I needed the practice, here's how you'd do it.

First, to make generating the combinations easier, we create a term to preprocess the lists to pair them with their lengths to avoid having to get the lengths multiple times. The cut avoids needless backtracking:

with_lengths([], []) :- !.
with_lengths([H|T1], [(Len, H)|T2]) :-
    length(H, Len),
    with_lengths(T1, T2).

Here's the comb/3 predicate, which you use for generating the combinations:

comb(L, R, Max) :-
    with_lengths(L, L1),
    comb1(L1, R, Max).

comb1/3 does the actual work. The comments explain what's going on:

% Combination works.
comb1([], [], 0).
% Try combining the current element with the remainder.
comb1([(Len, Elem)|T1], [Elem|T2], Max) :-
    NewMax is Max - Len,
    comb1(T1, T2, NewMax).
% Alternatively, ignore the current element and try
% combinations with the remainder.
comb1([_|T1], T2, Max) :-
    comb1(T1, T2, Max).
0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜