Finding the longest contiguous sublist in Prolog

Question

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

Answer 1

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