Обратная часть списка в прологе

Question

Моя цель для этой функции Пролога следующая:

Учитывая два списка, x и y, возвращают true, если y можно сформировать из x путем обращения непрерывной части списка x.

Например, если входное значение равно x = [1, 3, 2, 4], y = [1, 2, 3, 4], результат должен быть «истинным», потому что мы можем повернуть второй и третий элементы х, чтобы получить у.

Я действительно понятия не имею, и мне нужна помощь!

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

Answer 2

Алгоритмически вы можете сравнить оба из индекса 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 3

Это прологичный способ сделать это:

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.