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

问题描述

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

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

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

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

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

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.

它应该像这样工作:

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

推荐答案

首先，我们基于 bool01_t/2 :

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

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

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

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

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

请注意，max_of_by/3在平局情况下可能会成功多次:

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

将所有内容放在谓词maxCont/2中:

Put it all together in predicate maxCont/2:

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

示例查询:

?- 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屋！