Prolog - 查找列表列表(列表)的所有组合(产品)
Prolog - finding all combinations (The product) of List of Lists (of Lists)
我已经尝试了一些功能来实现一个可以找到所有组合的谓词,就像在那个例子中一样:
List = [[1, 2], [1, 2, 3]]
这些应该是输出,
Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]]
但我发现的所有解决方案都使用了 findall
,我不想在我的任务中使用它。
如何以不同的方式实现谓词,避免 findall
?
或者我如何在不使用任何内置功能的情况下实现 my_findall
?
A solution like here, without built-in predicates would be great
感谢帮手!
您可以使用 "The Craft of Prolog" 中的 findall 实现。但无论如何你最终都会使用内置的元谓词。
所以关于你的linked solution
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]].
我不太确定这是最有效的方法,但它相当透明。这里的想法是用递归(或归纳)"layers":
定义问题
% 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
或其他基于列表的预定义谓词的情况下解决问题。
我已经尝试了一些功能来实现一个可以找到所有组合的谓词,就像在那个例子中一样:
List = [[1, 2], [1, 2, 3]]
这些应该是输出,
Comb = [[1,1],[1,2],[1,3],[2,1],[2,2],[2,3]]
但我发现的所有解决方案都使用了 findall
,我不想在我的任务中使用它。
如何以不同的方式实现谓词,避免 findall
?
或者我如何在不使用任何内置功能的情况下实现 my_findall
?
A solution like here, without built-in predicates would be great
感谢帮手!
您可以使用 "The Craft of Prolog" 中的 findall 实现。但无论如何你最终都会使用内置的元谓词。
所以关于你的linked solution
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]].
我不太确定这是最有效的方法,但它相当透明。这里的想法是用递归(或归纳)"layers":
定义问题% 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
或其他基于列表的预定义谓词的情况下解决问题。