在 Prolog 中查找最长的连续子列表

本文介绍了在 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].