Swap last two elements of a list in Prolog

user_17628177 0
Viewed 275

I've been trying to write a program that compares two lists hat are the same except the last two elements of List 2 are in reverse order, i.e [4,5,6] and [4,6,5], and that returns the last two elements that have been swapped.

For example:

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

should return

X = [6, 5]

So far my code looks like this:

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

My predicate so far only takes two arguments and checks, if are the same except the last two elements of List 2 are in reverse order and returns true, if the condsitions are met

I don't know how I can modify my predicate to incoparate the X as its third argument and make it return the swapped elements.

prolog list
3 Answers

Try this:

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

Notice that by using the variable Rest in both subgoals, you establish that the lists must be the same, except for the last two items (which are swapped).

Example:

?- 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.
user_115359400

Using first-argument indexing, and improved performance by removing the unnecessary reverse(), and also 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).

Result in swi-prolog:

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

Performance comparison (this method is fastest):

?- 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)
user_176283360

I think the comparison made by @CapelliC [that has been deleted] is misleading. The OP asks for a predicate to compare two lists and check if they are the same, except for the last two elements that may appear swapped (which is different from a predicate that just swaps the last two elements of a single list). Thus, a fairer comparison should call the predicates to be compared with two instantiated lists as input.

My suggestion is to modify perf_belt/3 as follows:

/*  File:    last2swap_perf.pl
    Author:  Carlo
    Created: Dec 12 2021
    Purpose: compare answers to https://stackoverflow.com/q/70281408/874024
*/

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

Fairer results Running on SWI-Prolog, version 8.4.1, we can see that double reverse is not so bad.

?- 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.
user_115359400
Related