时间戳

首页 > 解决方案 > 查找列表的连续子列表

prolog - 查找列表的连续子列表

问题描述

我想编写一个谓词split/2来生成在另一个列表中找到的所有连续列表。

示例：split([1,2,3,4],X)应该返回 X = [4], X = [2,3],X = [1,2]等X = [1,2,3]。

到目前为止，我只有一个谓词可以返回列表的所有可能子列表：

sublist([],[]).
sublist([H|T], [H|R]) :-
    sublist(T,R).
sublist([_|T], R) :-
    sublist(T,R).

但是，对于示例中的查询，此谓词包含不需要的答案，例如[1,2,3,4] 中没有连续找到的X = [2,4]和。X = [1,3]

标签： prolog

解决方案

通常，如果将问题拆分为子问题，问题会更容易。我们可以首先构造一个谓词，它将构造给定列表的所有后缀。

我们可以如下构造这样的谓词：

suffix(_, []).
suffix([H|T], [H|T2]) :-
    suffix(T, T2).

所以对于列表中的每个点，我们可以决定停止（使用空列表），或者发出下一个项目。对于给定的样本列表，我们因此得到：

?- suffix([1,2,3,4],X).
X = [] ;
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4].

现在我们只需要决定什么时候开始后缀。对于列表中的每个项目，我们可以决定从该点开始，并枚举我们然后附加到该项目的所有后缀：

split([H|T], [H|S]) :-
    suffix(T, S).
split([_|T], S) :-
    split(T, S).

例如：

?- split([1,2,3,4],X).
X = [1] ;
X = [1, 2] ;
X = [1, 2, 3] ;
X = [1, 2, 3, 4] ;
X = [2] ;
X = [2, 3] ;
X = [2, 3, 4] ;
X = [3] ;
X = [3, 4] ;
X = [4] ;
false.

好消息是我们得到了第二个谓词“免费”：我们还可以获得列表的所有后缀。

我们可能还想包括空列表。我把它留作练习。

推荐阅读