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

Question

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

例如 - check([b,c],[a,b,c,d]) 必须返回 true 而 check([b,d],[a,b,c,d]) 必须返回 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).