Prolog - 查找列表清单(列表)的所有组合(产品)

Question

我尝试了一些功能来实现一个查找所有组合的谓词,例如:

List = [[1, 2], [1, 2, 3]]

这些应该是输出,

Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] 

但我发现的所有解决方案都在使用findall我不想在我的任务中使用的解决方案.

我怎样才能以不同的方式实现谓词,避免findall？

或者也许如何my_findall在不使用任何内置功能的情况下实现？

这里没有内置谓词的解决方案会很棒

感谢帮助!

Answer 1

我不太确定这是最有效的方法,但它相当透明.这里的想法是在递归(或归纳)"层"中定义问题:

% multiply_lists(ListOfLists, MultipliedListOfLists)
%
% The first two clauses handle the case where ListOfLists consists
%   of just one list
% The third clause handles the general case
%
multiply_lists([[X]], [[X]]).
multiply_lists([[X|Xs]], [[X]|T]) :- 
    multiply_lists([Xs], T).
multiply_lists([E|Es], R) :-
    multiply_lists(Es, R1),
    multiply_list(E, R1, R).

% multiply_list relates the product of a list of lists and a single list
%    of elements
%
multiply_list([], _, []).
multiply_list([E|Es], L, Ls) :-
    multiply_list(Es, L, LL),
    multiply_element(E, L, LL, Ls).

% multiply_element relates the product, prepended to a given list,
%   of a single list of lists and a single element 
%
multiply_element(_, [], A, A).
multiply_element(X, [Y|Ys], A, [[X|Y]|T]) :-
    multiply_element(X, Ys, A, T).

multiply_element/4 实际上将两个规则合并为一个:它定义了一个列表乘以一个元素,并将这些结果作为单个元素添加到给定列表中.

样本结果:

| ?- multiply_lists([[1, 2], [1, 2, 3]], L).

L = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]] ? ;

no
| ?- multiply_lists([[a,b,c], [1,2], [x,y]], L).

L = [[a,1,x],[a,1,y],[a,2,x],[a,2,y],[b,1,x],[b,1,y],[b,2,x],[b,2,y],[c,1,x],[c,1,y],[c,2,x],[c,2,y]] ? ;

no

上述实现的一些怪癖:

• 这不是尾递归(因此当列表变长时会使用更多堆栈)
• 它留下了一个选择点

但它确实说明了如何在不使用append/3或其他基于列表的预定义谓词的情况下解决问题.