Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
958 views
in Technique[技术] by (71.8m points)

list - Finding the longest contiguous sublist in Prolog

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].
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

First, we define z_nonsucc_t/3 based on 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 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 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].

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...