在 Prolog 中查找最长的连续子列表 [英] Finding the longest contiguous sublist in Prolog

问题描述

我是 Prolog 的初学者，这是我的问题:

我有一个无重复整数的排序列表，即 [1,2,3,11,12,13,14,21,22,23,24,25]

我想编写一个谓词来查找列表元素的最长连续子列表，即最长的列表，其中每个整数后跟其后续整数(在自然数集中).

在上面的示例中，此列表将是 [21,22,23,24,25] 其中 length = 5.

如果有多个列表具有相同的最大长度，我只对其中一个感兴趣，不管是哪一个.

它应该像这样工作:

maxCont([1,2,3,11,12,13,14,21,22,23,24,25],Lst]).Lst = [21,22,23,24,25].

解决方案

首先，我们根据clpfd 和 bool01_t/2:

<上一页>:- use_module(库(clpfd)).z_nonsucc_t(X,Y,T) :-Y #= X+1 #<==>乙，bool01_t(B,T).

要将整数列表拆分为连续的 runs，我们使用 splitlistIfAdj/3 像这样:

?- splitlistIfAdj(z_nonsucc_t,[1,2,3,11,12,13,14,21,22,23,24,25],Pss).Pss = [[1,2,3],[11,12,13,14],[21,22,23,24,25]].

接下来，我们定义 meta-predicate max_of_by/3 基于 if_/3，(#>)/3 和 (#>=)/3:

max_of_by(X,[E|Es],P_2) :-呼叫(P_2，E，V)，max_of_by_aux(Es,P_2,V,[E],Rs),反向(Rs，Xs)，成员(X，Xs).max_of_by_aux([]，_，_，Bs，Bs).max_of_by_aux([E|Es],P_2,V0,Bs0,Bs) :-呼叫(P_2，E，V)，if_(V#>V0, Bs1=[], Bs1=Bs0),if_(V #>= V0, (V1 = V , Bs2 = [E|Bs1]),(V1 = V0, Bs2 = Bs1)),max_of_by_aux(Es,P_2,V1,Bs2,Bs).

为了获得最长的列表，我们使用 元谓词 max_of_by/3 与 length/2 像这样:

?- max_of_by(Xs,[[1,2,3],[11,12,13,14],[21,22,23,24,25]],length).Xs = [21,22,23,24,25].

请注意，max_of_by/3 在相同的情况下可能会成功多次:

<上一页>?- max_of_by(Xs,[[1,2,3],[11,12,13,14,15],[21,22,23,24,25]],长度).Xs = [11,12,13,14,15];Xs = [21,22,23,24,25].

把它们放在谓词maxCont/2中:

maxCont(Zs,Xs) :-splitlistIfAdj(z_nonsucc_t,Zs,Pss),max_of_by(Xs,Pss,长度).

示例查询:

?- maxCont([1,2,3,11,12,13,14, 21,22,23,24,25],Xs).Xs = [21,22,23,24,25].?- maxCont([1,2,3,11,12,13,14,15,21,22,23,24,25],Xs).Xs = [11,12,13,14,15];Xs = [21,22,23,24,25].

I'm a beginner in Prolog and this is my question:

I have a sorted list of integers without duplicates i.e. [1,2,3,11,12,13,14,21,22,23,24,25]

I want to write a predicate that finds the longest contiguous sublist of the elements of the list, that is the longest list where each integer is followed by its subsequent integer (in the set of natural numbers).

In the above example this list would be [21,22,23,24,25] where length = 5.

In case there are more than one lists with the same maximum length, I'm interested in just one of them, no matter which.

It should work like this:

maxCont([1,2,3,11,12,13,14,21,22,23,24,25],Lst]).
Lst = [21,22,23,24,25].

解决方案

First, we define z_nonsucc_t/3 based on clpfd and bool01_t/2:

:- use_module(library(clpfd)).

z_nonsucc_t(X,Y,T) :-
   Y #= X+1 #<==> B,
   bool01_t(B,T).

To split an integer list into consecutive runs, we use splitlistIfAdj/3 like this:

?- splitlistIfAdj(z_nonsucc_t,[1,2,3,11,12,13,14,21,22,23,24,25],Pss).   
Pss = [[1,2,3],[11,12,13,14],[21,22,23,24,25]].

Next, we define meta-predicate max_of_by/3 based on if_/3, (#>)/3, and (#>=)/3:

max_of_by(X,[E|Es],P_2) :-
   call(P_2,E,V),
   max_of_by_aux(Es,P_2,V,[E],Rs),
   reverse(Rs,Xs),
   member(X,Xs).

max_of_by_aux([]    , _ ,_ ,Bs ,Bs).
max_of_by_aux([E|Es],P_2,V0,Bs0,Bs) :-
   call(P_2,E,V),
   if_(V #>  V0, Bs1=[], Bs1=Bs0),
   if_(V #>= V0, (V1 = V , Bs2 = [E|Bs1]),
                 (V1 = V0, Bs2 =    Bs1 )),
   max_of_by_aux(Es,P_2,V1,Bs2,Bs).

To get the longest list(s), we use meta-predicate max_of_by/3 with length/2 like so:

?- max_of_by(Xs,[[1,2,3],[11,12,13,14],[21,22,23,24,25]],length).
Xs = [21,22,23,24,25].

Note that max_of_by/3 may succeed more than once in tie cases:

?- max_of_by(Xs,[[1,2,3],[11,12,13,14,15],[21,22,23,24,25]],length).
  Xs = [11,12,13,14,15]
; Xs = [21,22,23,24,25].

Put it all together in predicate maxCont/2:

maxCont(Zs,Xs) :-
   splitlistIfAdj(z_nonsucc_t,Zs,Pss),
   max_of_by(Xs,Pss,length).

Sample queries:

?- maxCont([1,2,3,11,12,13,14,   21,22,23,24,25],Xs).
Xs = [21,22,23,24,25].

?- maxCont([1,2,3,11,12,13,14,15,21,22,23,24,25],Xs).
  Xs = [11,12,13,14,15]
; Xs = [21,22,23,24,25].

这篇关于在 Prolog 中查找最长的连续子列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！