list - 如何在Prolog中获取所有连续的子列表/子集？

Question

我想解决一个简单的问题，但即使我尝试了很多不同的方法，我也找不到解决方案。我正在使用 SICStus Prolog (如果这很重要)，并且我想获取列表的所有子列表/子集(我不知道哪个术语是正确的)，其中包含连续的元素。例如，如果我有列表 [1, 2, 3, 4]，则将 sl/2 谓词调用为 sl([1, 2, 3 , 4], R).，预期结果为:

? - sl([1, 2, 3, 4], R).
R = [] ? ;
R = [1] ? ;
R = [1, 2] ? ;
R = [1, 2, 3] ? ;
R = [1, 2, 3, 4] ? ;
R = [2] ? ;
R = [2, 3] ? ;
R = [2, 3, 4] ? ;
R = [3] ? ;
R = [3, 4] ? ;
R = [4] ? ;
no

到目前为止我能达到的最好结果是:

sl([], []).
sl([X|Xs], [X|Ys]) :-
    sl(Xs, Ys).
sl([_|Xs], Ys) :-
    sl(Xs, Ys).

但这还给我带来了以下不需要的结果:

R = [1,2,4] ? ;
R = [1,3,4] ? ;
R = [1,3] ? ;
R = [1,4] ? ;
R = [2,4] ? ;

我应该如何修改我的谓词才能获得所需的结果？

Answer 1

在 Prolog 中编写谓词时，您需要考虑谓词的含义，或者它定义的关系。您的谓词给出非解​​决方案的原因是您在谓词子句中混合了含义。它们的含义并不完全相同。

您有谓词sl/2，它的意思是“子列表”(或“子序列”)，但更重要的是，根据您提供的描述，它是一个< em>连续子列表(其中不能有任何“间隙”)。

现在我们可以分解您的条款:

sl([], []).

这表示空列表是空列表的连续子列表。这是事实，也是有效的事实。

sl([X|Xs], [X|Ys]) :-
    sl(Xs, Ys).

这表示如果 Ys 是连续的，则 [X|Ys] 是 [X|Xs] 的连续子列表Xs 的子列表。这种关系不成立。这里真正正确的是: [X|Ys] 是 [X|Xs] 的连续子列表 if Ys是 Xs 的连续前缀子列表。也就是说，Ys 不仅需要是 Xs 的子列表，而且只需要从列表的开头开始，而不是在此列表中的某个位置。这是一个线索，表明您需要另一个谓词，因为关系的含义不同。

您的最后一个子句表示，如果 Ys 是 的子列表，则 Ys 是 [_|Xs] 的子列表>Xs。这似乎是真的。

如果我们简单地调整上述更新的定义，我们会得到:

subseq([], []).
subseq([_|Xs], Ys) :-
    subseq(Xs, Ys).
subseq([X|Xs], [X|Ys]) :-
    prefix_subseq(Xs, Ys).

prefix_subseq(_, []).
prefix_subseq([X|Xs], [X|Ys]) :-
    prefix_subseq(Xs, Ys).

我在上面提供了 prefix_subseq/2 定义，但没有解释，但我认为你可以弄清楚。

现在产生:

| ?- subseq([a,b,c,d], R).

R = [a] ? a

R = [a,b]

R = [a,b,c]

R = [a,b,c,d]

R = [b]

R = [b,c]

R = [b,c,d]

R = [c]

R = [c,d]

R = [d]

R = []

(1 ms) yes

定义子列表(或子序列)的一种有趣、紧凑的方法是使用 append/2 谓词:

subseq(L, R) :- append([_, R, _], L).

这表示 L 是附加列表 _、R 和 _ 的结果。这个简单实现的小缺陷是，您将多次获得 R = [] ，因为它满足 append([_, R, _], L)以不止一种方式进行统治。

重新审视定义，您可以使用 DCG 来定义子序列，因为 DCG 非常适合处理序列:

% Empty list is a valid subsequence
subseq([]) --> ... .
% Subsequence is any sequence, followed by sequence we want, followed by any sequence
subseq(S) --> ..., non_empty_seq(S), ... .

% Definition of any sequence
... --> [] | [_], ... .

% non-empty sequence we want to capture
non_empty_seq([X]) --> [X].
non_empty_seq([X|T]) --> [X], non_empty_seq(T).

您可以使用phrase/2来调用它:

| ?- phrase(subseq(S), [a,b,c,d]).

S = [] ? ;

S = [a] ? ;

S = [a,b] ? ;

S = [a,b,c] ? ;

S = [a,b,c,d] ? ;

S = [b] ? ;

S = [b,c] ? ;

S = [b,c,d] ? ;

S = [c] ? ;

S = [c,d] ? ;

S = [d] ? ;

no

我们可以稍微重新调整这个定义，并使用通用的 seq//1 定义来使其更加紧凑:

subseq([]) --> seq(_) .
subseq([X|Xs]) --> seq(_), [X], seq(Xs), seq(_).

% alternatively: seq(_), seq([X|Xs]), seq(_).

seq([]) --> [].
seq([X|Xs]) --> [X], seq(Xs).