Swapping two items in a list

[babsetta21]

Hi,

I have a problem that I have been trying to solve for the past week.

I have to implement swap (X,Y,List,NList) which binds Nlist with List but with its Xth and Yth elements swapped.

eg. swap (2,4,[a,b,c,d,e],Final) binds Final to [a,d,c,b,e].


Below is the code I managed to write but it is still not working well obviously due to the Q and Z predicates...

swap(1,2,[H1,H2|Rest],[H2,H1|Rest]).
swap(X,Y,[H|T],Nlist):-Q is X-1,
Z is Y-1,
swap(Q,Z,T,Nlist),
Nlist=[H,Nlist].

Any help is sincerely appreciated!!!

 

[kahleen]

If your stopping condition is:

swap(1, 2, [H1, H2 | Rest], [H2, H1 | Rest]).

... are you sure you will always end up in this case? I mean, if you start with X = 2 and Y = 4 and you decrement them at each step, you will never get to a case where swap is called with 1 and 2 as first parameters.

A second observation would be that you can't do

Nlist = [H, Nlist]

This is possible in imperative languages and Nlist will be updated with a new value. In Prolog, you cannot reassign a variable once you have assigned it once. All subsequent assignments will usually fail.

What you should do in Prolog is make your recursive swap call return Nlist1 and then use Nlist1 to compute Nlist.

OK, now here is an idea of solving your problem.

Let's call your two elements X and Y and let's call their positions in the list Xpos and Ypos. You know Xpos and Ypos. Using Xpos, you could easily compute the sublist of elements that precede X and the sublist of elements that follow X in the main list, and you can also find X, like this:

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

Basically, this predicate takes MainList (the whole list) and Xpos as arguments and computes X (the first element to swap), A (the sublist that precedes X) and B (the sublist that follows X). A, X and B obey the rule A + [X | B] = MainList and the length of A is Xpos - 1, that's how we determined them.

Now if Xpos was smaller than Ypos, this means that Y is in our B list. From B and YPos using the same algorithm, you can determine the sublist BA preceding Y and the sublist BB following Y in B. Now you have 5 items that obey the rule:

A + [X] + BA + [Y] + BB = MainList

where A, BA and BB are lists and X and Y are the elements you need to swap

Now you just have to compute the result like this:

Result = A + [Y] + BA + [X] + BB

and return it (X and Y are swapped).

Please take this only as a suggestion. It is not the most efficient solution but it sure is the most easy to understand one