提取序列（列表）Prolog
Extracting sequences (Lists) Prolog
给定一个列表，例如 [1,2,3,7,2,5,8,9,3,4] 我如何提取列表中的序列？
一个序列被定义为一个有序列表（通常我会说 n-tuple 但我在 prolog 中被告知一个元组被称为一个序列）。所以我们想在下一个元素小于前一个元素的地方切割列表。
所以对于列表 [1,2,3,7,2,5,8,9,3,4] 它应该 return:
[ [1,2,3,7], [2,5,8,9], [3,4] ] %ie we have cut the list at position 4 & 8.
对于此练习，您不能使用结构 ; 或 ->
非常感谢！
示例结果：
eg1.
?-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] ]。
eg2.
?-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] ].
希望这有助于澄清问题。如果您需要进一步说明，请告诉我！再次感谢您提供的任何帮助。
评论中建议的 maplist/3 在这里对您没有帮助，因为 maplist/3 擅长获取列表并将每个元素映射到其他元素的相同大小的集合中，或者建立一个所有单个元素之间的关系均匀。在此问题中，您正在尝试收集具有特定属性的连续子列表。
这是一个 DCG 解决方案。这里的想法是将列表检查为一系列递增序列，其中在它们之间的边界处，先前序列的最后一个元素小于或等于以下序列的第一个元素（如问题陈述基本上所示） .
% A set of sequences is an increasing sequence ending in X
% followed by a set of sequences that starts with a value =< X
sequences([S|[[Y|T]|L]]) --> inc_seq(S, X), sequences([[Y|T]|L]), { X >= Y }.
sequences([S]) --> inc_seq(S, _).
sequences([]) --> [].
% An increasing sequence, where M is the maximum value
inc_seq([X,Y|T], M) --> [X], inc_seq([Y|T], M), { X < Y }.
inc_seq([X], X) --> [X].
partition(L, R) :- phrase(sequences(R), L).
| ?- partition([1,2,3,4,2,3,8,7], R).
R = [[1,2,3,4],[2,3,8],[7]] ? ;
(1 ms) no
| ?- partition([1,2,3,2,2,3,4,3],X).
X = [[1,2,3],[2],[2,3,4],[3]] ? ;
(1 ms) no
规则 sequences([]) --> []. 的唯一原因是您希望 partition([], []) 为真。否则，不需要该规则。
首先，让我们从概念上对其进行分解。谓词 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，可以 "succeed deterministically" 和 "use non-determinism when required"，视情况而定。
splitlistIfAdj/3 基于@false 在 this 答案中提出的 if_/3。所以传递给它的谓词必须遵守与 (=)/3 和 memberd_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...
给定一个列表，例如 [1,2,3,7,2,5,8,9,3,4] 我如何提取列表中的序列？
一个序列被定义为一个有序列表（通常我会说 n-tuple 但我在 prolog 中被告知一个元组被称为一个序列）。所以我们想在下一个元素小于前一个元素的地方切割列表。
所以对于列表 [1,2,3,7,2,5,8,9,3,4] 它应该 return:
[ [1,2,3,7], [2,5,8,9], [3,4] ] %ie we have cut the list at position 4 & 8.
对于此练习，您不能使用结构 ; 或 ->
非常感谢！
示例结果：
eg1.
?-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] ]。
eg2.
?-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] ].
希望这有助于澄清问题。如果您需要进一步说明，请告诉我！再次感谢您提供的任何帮助。
maplist/3 在这里对您没有帮助，因为 maplist/3 擅长获取列表并将每个元素映射到其他元素的相同大小的集合中，或者建立一个所有单个元素之间的关系均匀。在此问题中，您正在尝试收集具有特定属性的连续子列表。
这是一个 DCG 解决方案。这里的想法是将列表检查为一系列递增序列，其中在它们之间的边界处，先前序列的最后一个元素小于或等于以下序列的第一个元素（如问题陈述基本上所示） .
% A set of sequences is an increasing sequence ending in X
% followed by a set of sequences that starts with a value =< X
sequences([S|[[Y|T]|L]]) --> inc_seq(S, X), sequences([[Y|T]|L]), { X >= Y }.
sequences([S]) --> inc_seq(S, _).
sequences([]) --> [].
% An increasing sequence, where M is the maximum value
inc_seq([X,Y|T], M) --> [X], inc_seq([Y|T], M), { X < Y }.
inc_seq([X], X) --> [X].
partition(L, R) :- phrase(sequences(R), L).
| ?- partition([1,2,3,4,2,3,8,7], R).
R = [[1,2,3,4],[2,3,8],[7]] ? ;
(1 ms) no
| ?- partition([1,2,3,2,2,3,4,3],X).
X = [[1,2,3],[2],[2,3,4],[3]] ? ;
(1 ms) no
规则 sequences([]) --> []. 的唯一原因是您希望 partition([], []) 为真。否则，不需要该规则。
首先，让我们从概念上对其进行分解。谓词 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，可以 "succeed deterministically" 和 "use non-determinism when required"，视情况而定。
splitlistIfAdj/3 基于@false 在 this 答案中提出的 if_/3。所以传递给它的谓词必须遵守与 (=)/3 和 memberd_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...