倒车列表的一部分在序言

Question

我的目标，这Prolog的功能如下：

鉴于两个列表，x和y，返回true，如果Y可以从X通过反转列表x的连续的一部分形成。例如，如果输入是x = [1,3,2,4]，y = [1，2，3，4]，结果应该是“真”，因为我们可以将第二个和第三个x的元素得到y。

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

Answer 1

算法上，您可以比较两个索引0，并找出它们的不同之处（称为此索引“a”），并从n向后比较，直到它们不同（称为此索引“b”）。

然后在一个列表中将索引“a”反转为索引“b”，并比较列表（或子列表，无关紧要）以查看它们是否相同。如果是，则为真，否则为假。

当这两个列表完全相同时，就会出现转角情况。这可以被定义为真或假，取决于空集是否被视为列表的连续部分。

Search forward for mismatch: 
[1,2,3,4] 
[1,3,2,4] 
    ^-------a 

Search backward for mismatch: 
[1,2,3,4] 
[1,3,2,4] 
    ^-----b 

Reverse sub-list from a to b in either list: 
[1,3,2,4] <-- Reversed sub-list indexed from 1-2 
[1,3,2,4] 

If equal, then true. 

这有帮助吗？这假设有一个颠倒的子列表。

Answer 2

这是一个Prologish方式，您可以做到这一点：

rev(X,Y) :- 
    append(X1,X2,X3), 
    append(X3,X4,X), 
    reverse(X2,X5), 
    append(X1,X5,X6), 
    append(X6,X4,Y), 
    !. 

例子：

?- rev([1,3,2,4],[1,2,3,4]). 
true. 

?- rev([1,4,3,2],[1,2,3,4]). 
true. 

Answer 3

下面是使用SICStus序言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]) ? ...