Prolog

Question

我想检查列表 L1 的元素是否在列表 L2 中以相同的顺序连续出现。

例如 - check([b,c],[a,b,c,d]) 必须 return 为真，而 check([b,d],[a,b,c,d ]) 必须 return false

我查看了类似的帖子 Prolog - first list is sublist of second list? 并尝试了类似的解决方案但是每当我尝试检查元素是否存在时，我无法检查排序是否连续

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).
check( [X|XS], [_|XSS] ) :- sublist( [X|XS], XSS ).

如果我尝试检查顺序是否正确，那么我的代码就会出错。

check( [], _ ).
check( [X|XS], [X|XSS] ) :- sublist( XS, XSS ).

Answer 1

有趣的问题！我很惊讶它需要多少代码，所以可能有比这更好的解决方案。

首先我们需要一个助手来坚持一个列表是另一个列表的前缀。基本情况是我们从前缀列表中运行；归纳情况是当前项目匹配，两个列表的其余部分是前缀匹配。

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

现在查找连续的子列表相当于在列表中搜索前缀匹配项。如果当前项匹配，则有一个前缀是匹配项：

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

否则，我们只是丢弃搜索目标的这个元素并在子列表上重试：

consecutive_sublist(Prefix, [_|Ys]) :- consecutive_sublist(Prefix, Ys).

Answer 2

使用 append/3 谓词的实际标准定义的替代解决方案：

check(SubList, List) :-
    append(Prefix, _, List),
    append(_, SubList, Prefix).

调用示例：

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

no

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

true ? ;
no

| ?- check([b,c],[a,b,c,d,b,c,f]).

true ? ;
true ? ;
no

我们也可以使用这个定义来生成子列表-列表对：

| ?- check(SubList, List).

SubList = [] ? ;

List = [A|_]
SubList = [A] ? ;

List = [_|_]
SubList = [] ? ;

List = [A,B|_]
SubList = [A,B] ? ;

List = [_,A|_]
SubList = [A] ? ;

List = [_,_|_]
SubList = [] ? ;

List = [A,B,C|_]
SubList = [A,B,C] ? ;

List = [_,A,B|_]
SubList = [A,B] ? ;

...

这个问题还让您有机会了解谓词的终止属性。作为实验，交换 append/3 调用的顺序，然后检查回溯时发生的情况，例如前两个示例调用。

Answer 3

我们可以利用append/2 [swi-doc]一行一行地写成：

subsequence(X, Y) :-
    append([_,X,_], Y).

或者我们可以实现一个 subsequence/4 将两个变量 Prefix 和 Suffix 与子序列前后的列表统一起来：

subsequence(X, Y, Prefix, Suffix) :-
    append([Prefix,X,Suffix], Y).

因此我们有两个无关变量，它们将收集子序列前后的前缀和后缀。

Prolog - 第一个列表是第二个列表的子列表，同时保持顺序？

Prolog - first list is sublist of second list while maintaining order?

list

sublist