倒車列表的一部分在序言

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]) ? ...