在Prolog中交换列表的连续项 [英] Swapping consecutive items of a list in Prolog

问题描述

我正在尝试编写Prolog代码，该代码可以交换列表中的两个元素，但前提是它们彼此彼此连续.也就是说，

I'm trying to write Prolog code that can swap two elements of a list, but only if they are consecutive to each other. That is,

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不连续.)

should always fail (a and e are not consecutive.)

我可以假定一个项目仅出现在列表中一次.

我有以下代码，实际上可以正常工作:

I have the following code, which is actually working fine:

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新手才能编写.

However, just by looking at the code, I can tell that this is a horrible way to do this - repetitive, inefficient - something only a Prolog newbie like me could write.

任何有关如何改善此问题的建议将不胜感激！

Any suggestions on how to improve this would be greatly appreciated!

推荐答案

(请阅读重复和路德维希.这些都是很好的答案)

(Do read answers by repeat and Ludwig. Those are good answers)

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.

对于有许多可能的交换对的情况，它仅输出一次交换的所有方式. 该问题假定反正只能有一对.

For the case where there are many possible pairs to swap, it output all ways of swapping only once. The question assumes that there can only be one pair anyway.

?- 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).完全失败，请删除旧解决方案中的前两行，这样可以在不执行交换时将原始列表作为输出结束.

Modified to remove assumption 2

If you want the query conseq_swap(a, e, [a, g, d, e, f], X). to fail outright, remove the first two lines in the old solution, which allows the original list to end up as output when no swapping is performed.

这是基于以下假设编写的旧解决方案:

This is the old solution written with the following assumptions:

1. 输入不包含任何无界变量.
2. 当没有找到满足条件的对时，按原样输出输入列表，类似于问题中的代码.

1. The input does not contain any unbounded variable.
2. When no pair satisfying the condition is found, output the input list as-is, similar to what the code in the question does.

% 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).

这篇关于在Prolog中交换列表的连续项的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！