Замена последовательных элементов списка в Prolog

Я пытаюсь написать код на Прологе, который может поменять местами два элемента списка, но только если они последовательны друг другу. Это,

conseq_swap(d, e, [a, g, d, e, f], X).

должен дать:

X = [a, g, e, d, f].

(d и e идут подряд.)

Тем не мение,

conseq_swap(a, e, [a, g, d, e, f], X).

всегда должно терпеть неудачу (a и e не являются последовательными.)

Я могу предположить, что элемент появляется в списке только один раз.

У меня есть следующий код, который на самом деле работает нормально:

swap_conseq(X, Y, MainList, SwappedList) :-
   indexOf(MainList, X, Xpos),
   indexOf(MainList, Y, Ypos),
   Diff is Ypos - Xpos,
   Diff is 1,
   Xpos < Ypos,
   swap_ordered(X, Y, Xpos, Ypos, MainList, SwappedList).

swap_conseq(X, Y, MainList, SwappedList) :-
   indexOf(MainList, X, Xpos),
   indexOf(MainList, Y, Ypos),
   Diff is Xpos - Ypos,
   Diff is 1,
   Ypos < Xpos,
   swap_ordered(Y, X, Ypos, Xpos, MainList, SwappedList).

swap_ordered(Min, Max, Minpos, Maxpos, MainList, SwappedList) :-
   compute_lists(MainList, Min, Minpos, Pre, _),
   compute_lists(MainList, Max, Maxpos, _, Post),
   append(Pre, [Max, Min], Temp),
   append(Temp, Post, SwappedList).

indexOf([Element|_], Element, 1):- !.
indexOf([_|Tail], Element, Index):-
   indexOf(Tail, Element, Index1),
   !,
   Index is Index1+1.

compute_lists(MainList, X, Xpos, A, B) :-
   L is Xpos - 1,
   append(A, [X | B], MainList),
   length(A, L).

Однако, просто взглянув на код, я могу сказать, что это ужасный способ сделать это - повторяющийся, неэффективный - то, что может написать только новичок в Прологе, такой как я.

Любые предложения о том, как улучшить это, будут очень признательны!


prolog logic-programming
person Velvet Ghost    schedule 14.04.2013    source источник

Ответы (3)


arrow_upward
2
arrow_downward

(Прочитайте ответы repeat и Ludwig Это хорошие ответы)

Изменено, чтобы удалить оба предположения в старом решении.

conseq_swap(E1,E2,[E1,E2|R],[E2,E1|R]).
conseq_swap(E1,E2,[E2,E1|R],[E1,E2|R]).

conseq_swap(E1,E2,[A|RI],[A|RO]) :- conseq_swap(E1,E2,RI,RO).

Разрезы ((!)/0) удалены.

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[D,A,G,E,F],X), A=a,G=g,D=d,E=e,F=f.
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a,
G = g,
D = d,
E = e,
F = f,
X = [a, g, e, d, f] ;
false.

В случае, когда есть много возможных пар для обмена, он выводит все способы обмена только один раз. Вопрос предполагает, что в любом случае может быть только одна пара.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a, g, e, d, d, e, f] ;
X = [a, g, d, d, e, e, f] ;
X = [a, g, d, e, e, d, f] ;
false.

Изменено, чтобы удалить предположение 2

Если вы хотите, чтобы запрос conseq_swap(a, e, [a, g, d, e, f], X). полностью провалился, удалите первые две строки в старом решении, что позволяет исходному списку в конечном итоге быть выходным, когда не выполняется замена.

Старое решение (тот же вывод, что и рассматриваемый код)

Это старое решение, написанное со следующими предположениями:

  1. Входные данные не содержат неограниченных переменных.
  2. Если пара, удовлетворяющая условию, не найдена, выведите входной список как есть, подобно тому, как это делает код в вопросе.
% Empty list gives empty list
conseq_swap(_,_,[],[]). 

% List with single element gives back the same list
conseq_swap(_,_,[A],[A]) :- !.

% If we found the 2 items that need to be swapped, we can swap them.
% We don't check for the rest of the list, due to the
% assumption.
% The cut at the end signals that the rule below do not need to be checked.
conseq_swap(E1,E2,[E1,E2|R],[E2,E1|R]) :- !.
conseq_swap(E1,E2,[E2,E1|R],[E1,E2|R]) :- !.

% We recursively check the rest of the list and append the result.
conseq_swap(E1,E2,[A|RI],[A|RO]) :- conseq_swap(E1,E2,RI,RO).
person nhahtdh    schedule 15.04.2013
comment
@repeat: Есть ли недостатки в их использовании? И если у вас есть лучшее решение, почему бы не опубликовать его? И если вы не хотите публиковать - пожалуйста, дайте мне идею, как это улучшить. - person nhahtdh; 24.04.2015
comment
@повторяю: спасибо. Это конструктивная критика по сравнению с вашим первым комментарием. Для случая ?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f. я предполагаю, что список ограничен, хотя было бы интересно его поддержать. Во втором случае я согласен, что это ошибка. - person nhahtdh; 24.04.2015
comment
@repeat: я понимаю, что реализовал это на основе кода OP, который фактически возвращает исходный массив в случае сбоя. - person nhahtdh; 24.04.2015
comment
Это хорошие изменения, делающие ваш код более удобным, элегантным и понятным! +1! - person mat; 24.04.2015

arrow_upward
3
arrow_downward

Вот логически чистая реализация conseq_swap/4:

conseq_swap(E1,E2,Xs,Ys) :-       % use aux predicate w/dif-argument-order
   list_item1_item2_swapped(Xs,E1,E2,Ys).

По сравнению с conseq_swap/4 порядок аргументов list_item1_item2_swapped/4 изменен, поэтому индексация первого аргумента включен. Это может помочь предотвратить ненужные точки выбора.

list_item1_item2_swapped([],_,_,[]).  
list_item1_item2_swapped([X|Xs],E1,E2,Ys) :-
   list_prev_item1_item2_swapped(Xs,X,E1,E2,Ys).

Мы пропускаем дополнительный аргумент, который ссылается на предыдущий элемент списка, используя технику, обычно называемую "отставанием". Чтобы увидеть другое использование этой техники в действии, посмотрите @mat answer на некоторые другой вопрос о реализации предикатов в списках Prolog.

Фактическое отношение определяется list_prev_item1_item2_swapped/5:

list_prev_item1_item2_swapped([X|Xs],X0,X0,X,[X,X0|Xs]). % stop swapping
list_prev_item1_item2_swapped([X|Xs],X0,E1,E2,[X0|Ys]) :-
   dif(X0-X,E1-E2),               % state logically pure "not-equal"
   list_prev_item1_item2_swapped(Xs,X,E1,E2,Ys).

Сделанный! Теперь давайте запустим несколько запросов с помощью SWI-Prolog 7.1.37:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.                            % fails, as OP said it should

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a,g,e,d,f] ;                 % succeeds, as OP said it should
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a, G = g, D = d, E = e, F = f, X = [a,g,e,d,f] ;   % succeeds
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a,g,e,d,d,e,f] ;             % succeeds; only the 1st (d,e) pair is swapped
false.

Редактировать 2015-04-24

Вот более прямой, несколько деоптимизированный вариант кода, приведенного ранее.

Он менее эффективен, но, надеюсь, его легко читать людям. Такой же чистый, как и другой вариант.

conseq_swap(X0,X1,[X0,X1|Xs],[X1,X0|Xs]).
conseq_swap(E0,E1,[X0,X1|Xs],[X0|Ys]) :-
   dif(X0-X1,E0-E1),
   conseq_swap(E0,E1,[X1|Xs],Ys).

Те же запросы, те же ответы:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a,g,e,d,f] ;
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a, G = g, D = d, E = e, F = f, X = [a,g,e,d,f] ;
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a,g,e,d,d,e,f] ;
false.
person repeat    schedule 24.04.2015
comment
Узнайте что-то новое сегодня. +1 - person nhahtdh; 24.04.2015

arrow_upward
2
arrow_downward

Другое решение (в SWI-Prolog):

conseq_swap(D, E, L, Z) :- 
            append([A,[D,E],B], L),
            append([A,[E,D],B], Z).

Те же вопросы, те же ответы:

?- conseq_swap(a,e,[a,g,d,e,f],X).
false.

?- conseq_swap(d,e,[a,g,d,e,f],X).
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[A,G,D,E,F],X), A=a,G=g,D=d,E=e,F=f.
A = a,
G = g,
D = d,
E = e,
F = f,
X = [a, g, e, d, f] ;
false.

?- conseq_swap(d,e,[a,g,d,e,d,e,f],X).
X = [a, g, e, d, d, e, f] ;
X = [a, g, d, e, e, d, f] ;
false.

(Извините, если я не могу написать так много, как «повторить», но я итальянец).

person Ludwig    schedule 24.04.2015
comment
Спасибо за ценность моего решения. Я хочу указать, что мой последний комментарий был адресован другим людям, которые предпочли бы узнать больше об этом решении. Это не было нападением на вас! :) - person Ludwig; 24.04.2015