提取序列(列表) Prolog [英] Extracting sequences (Lists) Prolog

问题描述

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

Given a list eg [1,2,3,7,2,5,8,9,3,4] how would I extract the sequences within the list?

一个序列被定义为一个有序列表(通常我会说 n 元组，但我在序言中被告知一个元组被称为序列).所以我们想在下一个元素小于前一个元素的地方切割列表.

A sequence is defined as an ordered list (Normally I would say n-tuple but I have been told in prolog a tuple is referred to as a sequence). So we want to cut the list at the point where the next element is smaller than the previous one.

所以对于列表 [1,2,3,7,2,5,8,9,3,4] 它应该返回:

So for the list [1,2,3,7,2,5,8,9,3,4] it should return:

[ [1,2,3,7], [2,5,8,9], [3,4] ] %ie 我们已经在位置 4 处剪切了列表&8.

对于这个练习，你不能使用结构 ; 或 ->

For this exercise you CANNOT use the construct ; or ->

非常感谢！

示例结果:

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] ]. 

<小时>

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

---

Hopefully that helps clarify the problem. If you need further clarification just let me know! Thanks again in advance for any help you are able to provide.

推荐答案

首先，让我们从概念上分解它.谓词list_ascending_rest/3 定义了列表Xs、最大长度Ys 的最左边升序子列表和剩余项<代码>休息.我们将在以下查询中使用它:

First, let's break it down conceptually. The predicate list_ascending_rest/3 defines a relation between a list Xs, the left-most ascending sublist of maximum length Ys, and the remaining items Rest. We will use it like in the following query:

?- 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 直到没有剩余.

Then, let's implement predicate list_ascendingParts/2. This predicate repeatedly uses list_ascending_rest/3 for each part until nothing is left.

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

如果升序部分已知但列表未知怎么办?让我们来了解一下:

---

Edit 2015/04/05

What if the ascending parts are known but the list is unknown? Let's find out:

?- 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 的最一般查询:

And let's not forget about the most general query using 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 可以确定性地成功"和在需要时使用非确定性"，视情况而定.

By using the meta-predicate splitlistIfAdj/3 one can "succeed deterministically" and "use non-determinism when required", depending on the situation.

splitlistIfAdj/3 基于 if_/3，正如 这个 答案.因此传递给它的谓词必须遵守与 (=)/3 和 memberd_truth/3 相同的约定.

splitlistIfAdj/3 is based on if_/3 as proposed by @false in this answer. So the predicate passed to it has to obey the same convention as (=)/3 and 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:

Let's re-ask above queries, using splitlistIfAdj(#>=) instead of 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

最后，最通用的查询.我想知道答案是什么样的:

Last, the most general query. I wonder what the answers look like:

?- 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...

这篇关于提取序列(列表) Prolog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！