提取序列（列表） Prolog

Question

给定一个列表，例如[1,2,3,7,2,5,8,9,3,4]我如何提取列表中的序列？

序列被定义为有序列表（通常我会说 n 元组，但在序言中我被告知元组被称为序列）。因此，我们希望在下一个元素小于前一个元素的位置处剪切列表。

因此对于列表[1,2,3,7,2,5,8,9,3,4]它应该返回：

[ [1,2,3,7], [2,5,8,9], [3,4] ] %ie we have cut the list at position 4 & 8.

对于本练习，您不能使用构造;或->

提前谢谢了！

---

结果示例：

例如1。

?-function([1,2,3,7,2,5,8,9,3,4],X): %so we cut the list at position 4 & 9

X = [ [1,2,3,7], [2,5,8,9], [3,4] ]。

例如2。

?-function([1,2,3,2,2,3,4,3],X): %so we cut the list at position 3,4 & 8

X = [ [1,2,3], [2], [2,3,4], [3] ]. 

---

希望这有助于澄清问题。如果您需要进一步说明，请告诉我！再次感谢您能够提供的任何帮助。

Answer 1

首先，让我们从概念上对其进行分解。该谓词定义列表、最大长度的最左侧升序子列表和其余项目list_ascending_rest/3之间的关系。我们将像下面的查询一样使用它：XsYsRest

?- 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“确定性地成功” 和“在需要时使用非确定性”。

splitlistIfAdj/3基于此if_/3答案中@false 的提议。因此传递给它的谓词必须遵守与and相同的约定。(=)/3memberd_truth/3

那么让我们定义(#>)/3和(#>=)/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...