如何在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，意为“子列表”（或“子序列”），但更重要的是，根据您提供的描述，它是一个子列表，它是一个连续的子列表（其中不能有任何“空白”）。

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

sl([], []).

这表示空列表是空列表的连续子列表。的确如此，这是一个有效的事实。

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

这表示if 的连续子[X|Ys]列表是[X|Xs]if Ys的连续子列表Xs。这种关系是不正确的。怎样才是真正是真的在这里将是：[X|Ys]是的连续子列表[X|Xs]，如果Ys是一个连续的前缀子列表中Xs。也就是说，不仅Ys需要是的子列表Xs，还需要仅从列表的开始而不是列表的某个位置。这是一条线索，因为关系的含义不同，因此您需要另一个谓词。

您的最后一个子句说，这Ys是[_|Xs]if Ys的子列表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).