algorithm - 在 Prolog 中反转列表的一部分

Question

我对这个 Prolog 函数的目标如下:

给定两个列表 x 和 y，如果可以通过反转列表 x 的连续部分从 x 形成 y，则返回 true。

例如，如果输入是x = [1, 3, 2, 4], y = [1, 2, 3, 4]，结果应该是“true”，因为我们可以将第二个和第三个元素取反x 得到 y。

我真的不知道，我需要一些帮助!

Answer 1

这是使用 SICStus Prolog 4.3.1 的直接实现:

:- use_module(library(lists)).

list_singlePartReversed(Xs,Ys) :-
    same_length(Xs,Ys),              % Xs and Ys are lists w/the same length
    dif(Xs,Ys),                      % Xs and Ys are not equal
    append(Prefix  ,Xs0   ,Xs),      % Xs and Ys have common prefix
    append(Prefix  ,Ys0   ,Ys),
    append(Part    ,Suffix,Xs0),     % Xs and Ys have common suffix
    append(Reversed,Suffix,Ys0),
    reverse(Part,Reversed).          % the rest of Xs is reversed in Ys

现在开始一些示例查询...首先，您在问题中发布的原始查询:

?- list_singlePartReversed([1,3,2,4], [1,2,3,4]).
yes

接下来，一个我们预计会失败的简单案例:

?- list_singlePartReversed([1,4,3,2],[]).
no

所有可能的逆转方式如何？

?- list_singlePartReversed([1,2,3,4], Xs).
Xs = [2,1,3,4] ? ;
Xs = [3,2,1,4] ? ;
Xs = [4,3,2,1] ? ;
Xs = [1,3,2,4] ? ;
Xs = [1,4,3,2] ? ;
Xs = [1,2,4,3] ? ;
no

如果第一个参数没有实例化但第二个参数实例化了怎么办？

?- list_singlePartReversed(Xs, [1,2,3,4]).
Xs = [2,1,3,4] ? ;
Xs = [3,2,1,4] ? ;
Xs = [4,3,2,1] ? ;
Xs = [1,3,2,4] ? ;
Xs = [1,4,3,2] ? ;
Xs = [1,2,4,3] ? ;
no

最一般的查询呢？我们是否得到了无限解集的公平枚举？

?- list_singlePartReversed(Xs,Ys).
Xs = [_A,_B],       Ys = [_B,_A],       prolog:dif([_A,_B],[_B,_A])             ? ;
Xs = [_A,_B,_C],    Ys = [_B,_A,_C],    prolog:dif([_A,_B,_C],[_B,_A,_C])       ? ;
Xs = [_A,_B,_C],    Ys = [_C,_B,_A],    prolog:dif([_A,_B,_C],[_C,_B,_A])       ? ;
Xs = [_A,_B,_C],    Ys = [_A,_C,_B],    prolog:dif([_A,_B,_C],[_A,_C,_B])       ? ;
Xs = [_A,_B,_C,_D], Ys = [_B,_A,_C,_D], prolog:dif([_A,_B,_C,_D],[_B,_A,_C,_D]) ? ...