如何在 Prolog 中获取所有连续的 sublists/subsets？

Question

我想解决一个简单的问题，但即使我尝试了很多不同的方法，我也找不到解决方案。我正在使用 SICStus Prolog（如果重要的话），我想获取列表的所有 sublists/subsets（我不知道哪个术语是正确的），其中包含连续的元素。例如，如果我有列表 [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，它的意思是 "sublist"（或 "subsequence"），但除此之外，还意味着根据您提供的描述的子列表，这是一个连续子列表（其中不能有任何 "gaps"）。

现在我们可以分解你的子句了：

sl([], []).

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

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

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

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

如何在 Prolog 中获取所有连续的 sublists/subsets？

How to get all consecutive sublists/subsets in Prolog?

substring

list

prolog

sublist