Reversing Part of a List in Prolog

My goal for this Prolog function is as follows:

Given two lists, x and y, return true if y can be formed from x by reversing a contiguous part of list x.

For example, if the input is x = [1, 3, 2, 4], y = [1, 2, 3, 4], the result should be "true" because we c开发者_如何学Pythonan reverse the second and third elements of x to get y.

I really have no idea, and I need some help!

Here's a straight-forward implementation using 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

Now on to some sample queries... First, the original query you posted in the question:

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

Next, a simple case we expect to fail:

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

What about all possible ways to do the reversal?

?- 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

What if the first argument is not instantiated but the second one is?

?- 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

And what about the most general query? Do we get a fair enumeration of the infinite solution set?

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

Algorithmically, you can compare both from index 0, and find where they differ (call this index "a"), and compare backwards from n, until they differ (call this index "b").

Then reverse from index "a" to index "b" in one list, and compare the lists (or sub-list, it doesn't matter) to see if they are the same. If so, then true, otherwise false.

A corner case would be when both lists are identical. This could be be defined as either true or false, depending on whether a null set counts as a contiguous part of a list.

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.

Does that help? This assumes that there is a single reversed sub-list.

This is a Prologish way you can do it:

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

Examples:

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

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