prolog - 寻找子序列对

Question

以下函数的目的是找到长度为 2 的子序列的匹配对。例如。 [1,2,3,4,2,3,5] 有一对匹配的 [2,3]。如果我提供一个没有匹配对的序列，则第一个函数会出现内存溢出，但第二个函数会很快完成。

为什么存在差异，是否有一种通用技术可以深入研究此类问题？

repeat_pair(Items) :-
    append(_,[X,Y|_],Left),
    append(Left,[X,Y|_],Items).

repeat_pair(Items) :-
    append(Left,[X,Y|_],Items),
    append(_,[X,Y|_],Left).

Answer 1

正如您在评论中观察到的，在第一个变体中，Items 之间没有关系。和目标append(_, [X,Y|_], Left) ，因此回溯这个目标将枚举其所有无限多的解决方案。

您的第二种方法是解决此问题的最佳方法，但实际上通常您有时需要以其他方式限制搜索空间。

第一个子句的问题是 Left是完全不受约束的。但我们知道我们永远不希望它长于 Items .所以我们可以写一个谓词来表达“Items 是一个列表，Left 是一个更短或等长的列表”:

list_shorterorequal(_List, []).
list_shorterorequal([_|List], [_|ShorterOrEqual]) :-
    list_shorterorequal(List, ShorterOrEqual).

?- list_shorterorequal([a, b, c], ShorterOrEqual).
ShorterOrEqual = [] ;
ShorterOrEqual = [_G938] ;
ShorterOrEqual = [_G938, _G941] ;
ShorterOrEqual = [_G938, _G941, _G944].

然后你可以像这样调整你的第一个实现:

repeat_pair_1x(Items) :-
    list_shorterorequal(Items, Left),
    append(_,[X,Y|_],Left),
    append(Left,[X,Y|_],Items).

这成功了一次，然后迅速终止:

?- repeat_pair_1x([1,2,3,4,2,3,5]).
true ;
false.

如果您的 Prolog 有 between/3谓词(他们通常这样做)，您也可以使用它来限制 Left 的长度在我们对 Left 有任何了解之前本身:

repeat_pair_2x(Items) :-
    length(Items, ItemsLength),
    between(2, ItemsLength, LeftLength),
    length(Left, LeftLength),
    append(_,[X,Y|_],Left),
    append(Left,[X,Y|_],Items).

这也很好地结束了:

?- repeat_pair_2x([1,2,3,4,2,3,5]).
true ;
false.

请注意，这两个谓词在最一般的查询中的行为略有不同，并且通常如果调用的参数未绑定(bind)到有限列表:

?- repeat_pair_1x(Items).
Items = [_G918, _G924, _G918, _G924|_G940] ;
Items = [_G918, _G924, _G930, _G918, _G924|_G946] ;
Items = [_G918, _G924, _G930, _G924, _G930|_G949] ;
Items = [_G918, _G924, _G930, _G936, _G918, _G924|_G952] ;
Items = [_G918, _G924, _G930, _G936, _G924, _G930|_G955] .

?- repeat_pair_2x(Items).
Items = [_G918, _G921, _G918, _G921] ;
Items = [_G918, _G921, _G918, _G921, _G930] ;
Items = [_G918, _G921, _G924, _G918, _G921] ;
Items = [_G918, _G921, _G924, _G921, _G924] ;
Items = [_G918, _G921, _G918, _G921, _G930, _G933] .

调用 length/2在 Items在第二个变体中，我们强制它是一个有限列表。在某些情况下，您可能不希望这样做。