在Prolog中交换列表中的最后两个元素。

Question

我尝试编写一个程序，比较两个列表，这两个列表除了 List 2 的倒数第二和倒数第三个元素顺序相反外都相同。例如，[4,5,6] 和 [4,6,5]，并返回被交换的最后两个元素。

SwapLastTwo([4, 5, 6] , [ 4, 6, 5], X).

应该返回

X = [6, 5]

到目前为止，我的代码看起来是这样的：

lastTwoReversed([Z,A|T],[_,Y,X]) :-reverse([Z,A|T],[Y,X|_]).

目前，我的谓词只有两个参数，并检查是否满足以下条件：除了列表2的最后两个元素以相反的顺序排列外，两个列表是否完全相同。如果满足条件，则返回true。

我不知道如何修改我的谓词，以将X作为第三个参数并使其返回交换后的元素。

- BillyRater

Answer 1

请尝试以下操作：

lastTwoReversed(L1, L2, [X1,X2]) :-
    reverse(L1, [X1,X2|Rest]),
    reverse(L2, [X2,X1|Rest]).

注意在两个子目标中都使用变量 Rest，这样可以确保这两个列表除了最后两个元素被交换之外，其余部分完全相同。

示例：

?- lastTwoReversed([1,2,3,4,5,6], [1,2,3,4,6,5], R).
R = [6, 5].

?- lastTwoReversed([1,2,3,4,5,6], [1,2,3,6,5], R).
false.

?- lastTwoReversed([1,2,3,4,5,6], [1,2,3,4,5,6], R).
false.

- slago

---

也许这一切都是关于成为卓越的支配者...哈哈 https://dev.to/facundocorradini/why-i-don-t-use-stack-overflow-1f0l - slago

仅为了说明上下文，我上面的评论是回答一个用户问我为什么有人会对一个好的解决方案进行投票（在我的解决方案被投票后）。该问题已被删除。 - slago

Answer 2

使用第一个参数索引，并通过删除不必要的reverse()和same_length()来提高性能：

swap_last_2([Elem1, Elem2|Tail], SwappedLst, Last2) :-
    % same_length would prevent an unwanted choicepoint on: swap_last_2(L, [a,b], SL).
    %same_length([Elem1, Elem2|Tail], SwappedLst),
    swap_last_2_(Tail, Elem1, Elem2, SwappedLst, Last2).


% Swap the last 2 elements
swap_last_2_([], Elem1, Elem2, [Elem2, Elem1], [Elem2, Elem1]).

swap_last_2_([Head|Tail], Elem1, Elem2, [Elem1|SwappedLst], Last2) :-
    % Move the elements along
    swap_last_2_(Tail, Elem2, Head, SwappedLst, Last2).

swi-prolog 的结果:

?- swap_last_2([4, 5, 6], [4, 6, 5], X).
X = [6,5].

性能比较（此方法最快）：

?- cmp(1000, 1000).
% 7,011,001 inferences, 0.503 CPU in 0.497 seconds (101% CPU, 13941510 Lips)
% 2,001,001 inferences, 0.282 CPU in 0.278 seconds (101% CPU, 7098617 Lips)
% 2,007,001 inferences, 0.205 CPU in 0.203 seconds (101% CPU, 9782721 Lips)
% 1,002,001 inferences, 0.063 CPU in 0.063 seconds (101% CPU, 15819840 Lips)

- brebs

---

我已经为你的答案点赞，但我认为 same_length/2 的调用并不是必要的：如果 swap_last_2_/2 最终导致第一个列表为空，而第二个列表恰好有两个项，则说明作为输入提供给 swap_last_2/2 的列表确实具有相同的长度。通过消除这个调用，你将拥有更快的代码 [尽管它仍然具有时间复杂度 O(n)]。 - slago

@slago 是的，我已经注释掉了same_length/2，以获得更好的性能。在昨天的版本中，它是为了防止无限循环而需要的，但现在仅仅是为了防止不必要的选择点。 - brebs

Answer 3

我认为@CapelliC制作的比较已经被删除，这是误导性的。原帖要求一个谓词来比较两个列表并检查它们是否相同，除了最后两个元素可能出现交换（这与只交换单个列表的最后两个元素的谓词是不同的）。因此，更公正的比较应该使用两个实例化的列表作为输入来调用要比较的谓词。

我的建议是将perf_belt/3修改如下：

/*  File:    last2swap_perf.pl
    Author:  Carlo
    Created: Dec 12 2021
    Purpose: compare answers to https://dev59.com/HMLra4cB1Zd3GeqPWP2Z
*/

:- module(last2swap_perf, [cmp/2]).

:- meta_predicate perf_belt(+,+,3).

% CapelliC's solutions

% append/2 based

last2swap_app2(A,B,[U,V]):-
    append([C,[U,V]],A),
    append([C,[V,U]],B).

% append/3 based

last2swap_app3(A,B,[U,V]):-
    append(C,[U,V],A),
    append(C,[V,U],B).

% slago' solution

lastTwoReversed(L1, L2, [X1,X2]) :-
    reverse(L1, [X1,X2|Rest]),
    reverse(L2, [X2,X1|Rest]).

% brebs' answer

swap_last_2([Elem1, Elem2|Tail], SwappedLst, Last2) :-
    swap_last_2_(Tail, Elem1, Elem2, [], RevSwappedLst, Last2),
    reverse(RevSwappedLst, SwappedLst).

% This swaps the last 2 elements

swap_last_2_([], Elem1, Elem2, SoFar, [Elem1, Elem2|SoFar], [Elem2, Elem1]).

swap_last_2_([Head|Tail], Elem1, Elem2, SoFar, SwappedLst, Last2) :-
    % Move the elements along
    swap_last_2_(Tail, Elem2, Head, [Elem1|SoFar], SwappedLst, Last2).

%!  %%% minimal perf utility

perf_belt(NRep, LList, Pred) :-       % <== NEW VERSION PROPOSED
    make_lists(LList, List1, List2), 
    time( forall(between(1, NRep, _), % <== TWO INSTANTIATED LISTS AS INPUT 
                 call(Pred, List1, List2, _)) ).

make_lists(N, List1, List2) :-
    N1 is N - 1,
    N2 is N - 2,
    numlist(1, N2, Prefix),
    append(Prefix, [N1, N], List1),
    append(Prefix, [N, N1], List2).

cmp(NRep,LList) :-
    perf_belt(NRep,LList,last2swap_app2),
    perf_belt(NRep,LList,last2swap_app3),
    perf_belt(NRep,LList,lastTwoReversed),
    perf_belt(NRep,LList,swap_last_2).

更公平的结果 在运行SWI-Prolog 8.4.1版本时，我们可以看到双重反转并不那么糟糕。

?- cmp(100, 100).
% 71,101 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
% 20,101 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
% 20,701 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
% 20,401 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
true.

?- cmp(100, 1000).
% 701,101 inferences, 0.047 CPU in 0.047 seconds (100% CPU, 14956821 Lips)
% 200,101 inferences, 0.031 CPU in 0.031 seconds (100% CPU, 6403232 Lips)
% 200,701 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 12844864 Lips)
% 200,401 inferences, 0.016 CPU in 0.016 seconds (100% CPU, 12825664 Lips)
true.

?- cmp(1000, 1000).
% 7,011,001 inferences, 0.438 CPU in 0.437 seconds (100% CPU, 16025145 Lips)
% 2,001,001 inferences, 0.219 CPU in 0.219 seconds (100% CPU, 9147433 Lips)
% 2,007,001 inferences, 0.141 CPU in 0.141 seconds (100% CPU, 14272007 Lips)
% 2,004,001 inferences, 0.141 CPU in 0.141 seconds (100% CPU, 14250674 Lips)
true.

- slago

---

你说得对，是我的错，使用了未实例化的参数，导致回溯。抱歉给大家带来困扰。 - CapelliC

@CapelliC 没问题！实际上我必须感谢你！你的答案帮助澄清了这个问题，因为我的答案被那些认为它太低效的人批评了。 - slago

我通过移除一个reverse()函数来改进我的代码，因此现在它的速度显著提高了。 - brebs

@brebs 不错！每次调用reverse/2（完整列表遍历）的时间复杂度为O（n）。因此，通过消除一次这样的调用（并同时遍历两个列表，就像你所做的那样），实际上预计会获得这种效率提升。然而，请注意，算法的时间复杂度仍然是O（n）。这个新版本的优势仅仅在于一个常数因子（似乎小于2）。 - slago