首先,让我们从概念上对其进行分解。谓词list_ascending_rest/3
定义列表之间的关系Xs
,最左边的最大长度的升序子列表Ys
,以及剩余的项目Rest
。我们将像下面的查询一样使用它:
?- Xs = [1,2,3,7,2,5,8,9,3,4], list_ascending_rest(Xs,Ys,Rest).
Ys = [1,2,3,7],
Rest = [2,5,8,9,3,4] ;
false.
直接的谓词定义如下:
:- use_module(library(clpfd)).
list_ascending_rest([],[],[]).
list_ascending_rest([A],[A],[]).
list_ascending_rest([A1,A2|As], [A1], [A2|As]) :-
A1 #>= A2.
list_ascending_rest([A1,A2|As], [A1|Bs], Cs) :-
A1 #< A2,
list_ascending_rest([A2|As], Bs,Cs).
然后,让我们实现谓词list_ascendingParts/2
。该谓词重复使用list_ascending_rest/3
对于每个部分,直到什么都没有剩下。
list_ascendingParts([],[]).
list_ascendingParts([A|As],[Bs|Bss]) :-
list_ascending_rest([A|As],Bs,As0),
list_ascendingParts(As0,Bss).
示例查询:
?- list_ascendingParts([1,2,3,7,2,5,8,9,3,4],Xs).
Xs = [[1,2,3,7], [2,5,8,9], [3,4]] ;
false.
?- list_ascendingParts([1,2,3,2,2,3,4,3],Xs).
Xs = [[1,2,3], [2], [2,3,4], [3]] ;
false.
编辑2015/04/05
如果升序部分已知但列表未知怎么办?让我们来了解一下:
?- list_ascendingParts(Ls, [[3,4,5],[4],[2,7],[5,6],[6,8],[3]]).
Ls = [3,4,5,4,2,7,5,6,6,8,3] ? ;
no
我们不要忘记最常见的查询list_ascendingParts/2
:
?- assert(clpfd:full_answer).
yes
?- list_ascendingParts(Ls, Ps).
Ls = [], Ps = [] ? ;
Ls = [_A], Ps = [[_A]] ? ;
Ls = [_A,_B], Ps = [[_A],[_B]], _B#=<_A, _B in inf..sup, _A in inf..sup ? ...
编辑2015-04-27
有改进的余地吗?是的,确实!
通过使用元谓词splitlistIfAdj/3 https://stackoverflow.com/a/29867514/4609915一个人可以“确定性地成功”and“在需要时使用非确定性”,具体取决于情况。
splitlistIfAdj/3
是基于if_/3
正如 @false 中所提议的this https://stackoverflow.com/a/27358600/4609915回答。因此传递给它的谓词必须遵守与(=)/3
and memberd_truth/3
.
那么我们来定义一下(#>)/3
and (#>=)/3
:
#>=(X,Y,Truth) :- X #>= Y #<==> B, =(B,1,Truth).
#>( X,Y,Truth) :- X #> Y #<==> B, =(B,1,Truth).
让我们重新询问上面的查询,使用splitlistIfAdj(#>=)
代替list_ascendingParts
:
?- splitlistIfAdj(#>=,[1,2,3,7,2,5,8,9,3,4],Pss).
Pss = [[1,2,3,7],[2,5,8,9],[3,4]]. % succeeds deterministically
?- splitlistIfAdj(#>=,[1,2,3,2,2,3,4,3],Pss).
Pss = [[1,2,3],[2],[2,3,4],[3]]. % succeeds deterministically
?- splitlistIfAdj(#>=,Ls,[[3,4,5],[4],[2,7],[5,6],[6,8],[3]]).
Ls = [3,4,5,4,2,7,5,6,6,8,3] ; % works the other way round, too
false. % universally terminates
最后,最常见的查询。我想知道答案是什么样的:
?- splitlistIfAdj(#>=,Ls,Pss).
Ls = Pss, Pss = [] ;
Ls = [_G28], Pss = [[_G28]] ;
Ls = [_G84,_G87], Pss = [[_G84],[_G87]], _G84#>=_G87 ;
Ls = [_G45,_G48,_G41], Pss = [[_G45],[_G48],[_G41]], _G45#>=_G48, _G48#>=_G41
% and so on...