Reversing Part of a List in Prolog

Question

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 can reverse the second and third elements of x to get y.

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

Answer 1

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.

Answer 2

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.