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或其他基于列表的预定谓词的情况下解决问题。

Answer 2

您可以使用" Prolog of of Prolog"的Findall实现。但是无论如何，您最终都会使用内置的元谓词。

因此，关于您的链接解决方案

try([],[]).
try([L|Ls],[M|Ms]):-
  member(M,L),
  try(Ls,Ms).
findall2( Template, Enumerator, List ) :-
  asserta( 'find all'( [] ) ),
  call( Enumerator ),
  asserta( 'find all'( {Template} ) ),
  fail
;
  all_found( [], List ).

all_found( SoFar, List ) :-
  retract('find all'( Item ) ),
  !,
  /*  to stop retract looking for more Items.  */
  all_found( Item, SoFar, List ).

all_found( [], List, List ).
all_found( {Template}, SoFar, List ) :-
  all_found( [Template|SoFar], List ).

所以你会得到

?- List = [[1, 2], [1, 2, 3]], findall2(M,try(List,M),Comb).
List = [[1, 2], [1, 2, 3]],
Comb = [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3]].