list - 在序言列表中查找逐渐变大的元素

Question

给定一个序言列表，我想创建第二个包含逐渐变大元素的序言列表。例如，

L = [ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ]

Answer = [ 1, 5, 10, 15, 20 ]

我的代码:

local_max([],_,_).
local_max([XH|XT],Y,temp) :-
    ( XH =< temp ->
      local_max(XT,Y,temp)
      ;
      local_max(XT,[XH|Y],XH)
    ).

我认为这应该使我的回答完全颠倒，但事实并非如此。
只是假的。

该列表仅包含正整数，所以我只是做了

local_max([ 1, 5, 2, 3, 4, 10, 15, 11, 12, 13, 20 ],Answer,0).

Answer 1

由于您使用的是 Prolog 的 (;)/2 - if-then-else 对于该任务，您不妨考虑 if_/3 .此外，使用 CLP(FD) 可以使谓词更加通用(有关详细信息，请参见例如 Swi-Prolog 手册的 entry on CLP(FD) )。此外，我建议使用带有两个参数的调用谓词，即递增元素的列表和子列表。为了强调谓词的关系性质，让我们给它一个更具描述性的名称，比如 list_ascendings/2:

:- use_module(library(clpfd)).

list_ascendings([],[]).
list_ascendings([X|Xs],A) :-
   X0 #= X-1,
   list_ascendings_([X|Xs],A,X0).

list_ascendings/2 的第一条规则用于处理空列表。如果您不想包含这种情况，请忽略该规则。第二条规则调用谓词 list_ascendings_/3 的枢轴值 ( X0 ) 小于列表的头部，因此后者包含在递增元素的子列表中。大于关系的具体化版本(用作 if_/3 的第一个参数)可以这样定义:

bool_t(1,true).
bool_t(0,false).

#<(X,Y,Truth)  :- X #< Y #<==> B, bool_t(B,Truth).

在此基础上，描述实际关系的谓词可以这样定义:

list_ascendings_([],[],_).
list_ascendings_([X|Xs],A,X0) :-
   if_(X0#<X, (A=[X|As], X1=X), (A=As, X1=X0)), 
   list_ascendings_(Xs,As,X1).

根据枢轴值是否小于列表的头部，相应地描述升序元素列表( A )和新的枢轴值( X1 )。

现在让我们看看谓词是如何工作的。您的示例查询产生所需的结果:

   ?- list_ascendings([1,5,2,3,4,10,15,11,12,13,20],A).
A = [1,5,10,15,20]

请注意，如果第一个参数是ground，则谓词确定性地成功(没有选择点打开，因此无需在唯一解之后按 ;)。你也可以问相反的问题:哪些列表有 [1,5,10,15,20]作为最大的递增子列表？

   ?- list_ascendings(L,[1,5,10,15,20]).
L = [1,5,10,15,20] ? ;
L = [1,5,10,15,20,_A],
_A in inf..20 ? ;
L = [1,5,10,15,20,_A,_B],
_A in inf..20,
_B in inf..20 ? 
...

显然，这个问题有无数个答案。但是，最好以更公平的顺序获得答案，即长度为 6 的列表的所有答案都在长度为 7 的列表之前，依此类推。您可以通过在查询前加上目标长度/2 来实现:

   ?- length(L,_), list_ascendings(L,[1,5,10,15,20]).
L = [1,5,10,15,20] ? ;
L = [1,5,10,15,20,_A],
_A in inf..20 ? ;
L = [1,5,10,15,_A,20],
_A in inf..15 ? ;
L = [1,5,10,_A,15,20],
_A in inf..10 ? ;
...
L = [1,5,10,15,20,_A,_B],
_A in inf..20,
_B in inf..20 ? ;
L = [1,5,10,15,_A,20,_B],
_A in inf..15,
_B in inf..20 ? ;
L = [1,5,10,15,_A,_B,20],
_A in inf..15,
_B in inf..15 ? ;
...

也可以通过限制 L的元素得到具体数字的答案。使用 ins/2 并标记它的域。例如:有哪些长度为 7 的列表和 0 到 20 之间的数字使得 [1,5,10,15,20]是最大的递增子列表吗？相应的查询提供了所有 1997 年的答案:

   ?- length(L,7), L ins 0..20, list_ascendings(L,[1,5,10,15,20]), label(L).
L = [1,5,10,15,20,0,0] ? ;
L = [1,5,10,15,20,0,1] ? ;
L = [1,5,10,15,20,0,2] ? ;
...
L = [1,5,10,15,20,2,15] ? ;
...
L = [1,0,5,10,4,15,20] ? ;
...

编辑:

关于评论中的问题，从升序版本中描述逐渐降序的子列表非常简单。你只需要稍微改变两个目标:

list_descendings([],[]).
list_descendings([X|Xs],A) :-
   X0 #= X+1,                                     % <- change
   list_descendings_([X|Xs],A,X0).

list_descendings_([],[],_).
list_descendings_([X|Xs],A,X0) :-
   if_(X#<X0, (A=[X|As], X1=X), (A=As, X1=X0)),   % <- change
   list_descendings_(Xs,As,X1).

这会产生预期的结果:

   ?- list_descendings([20,15,3,5,7,8,2,6,2],A).
A = [20,15,3,2]

另一方面，如果您的意思是一个谓词同时执行这两种操作(请参阅下面的最后一个查询)，您需要进行更多更改。首先，您需要为降序子列表添加关系的具体化版本:

#>(X,Y,Truth)  :- X #> Y #<==> B, bool_t(B,Truth).

由于升序和降序子列表的第一个枢轴值的计算方式不同，因此可以将其委托(delegate)给一个新的谓词:

x_pivot_wrt(X,X0,#>) :- X0 #= X+1.
x_pivot_wrt(X,X0,#<) :- X0 #= X-1.

然后调用谓词需要一个额外的参数来指定子列表应针对哪个关系进行。重命名它以反射(reflect)其新行为也是有利的:

list_progressives_wrt([],[],_).
list_progressives_wrt([X|Xs],P,Rel) :-
   x_pivot_wrt(X,X0,Rel),
   list_progressives_wrt_([X|Xs],P,Rel,X0).

最后，描述实际关系的谓词还有一个附加参数，即指定关系。 if_/3 的第一个参数调用指定的关系 ( Rel ) 以及枢轴值 ( X0 ) 和列表的头部 ( X )。请注意，该调用缺少最后一个参数(真值)，就像 if_/3 的第一个参数一样。在 list_ascendings_/3 和 list_descendings_/3 中。

list_progressives_wrt_([],[],_,_).
list_progressives_wrt_([X|Xs],P,Rel,X0) :-
   if_(call(Rel,X0,X), (P=[X|Ps], X1=X), (P=Ps, X1=X0)),
   list_progressives_wrt_(Xs,Ps,Rel,X1).

与您的示例对应的查询会产生所需的结果:

   ?- list_progressives_wrt([1,5,2,3,4,10,15,11,12,13,20],P,#<).
P = [1,5,10,15,20]

由于可以指定的关系出现在 x_pivot_wrt/3 中，因此您可以通过保留最后一个参数变量来请求这两种变体:

   ?- list_progressives_wrt([20,15,3,21,5,7,8,2,6,30,2],P,Rel).
P = [20,15,3,2],
Rel = #> ? ;
P = [20,21,30],
Rel = #<