CODEWITHSUNDEEP
listprologswap
user3649515
user3649515

Reputation: 199

Swap two elements from list with specified indices

I need to swap two elements in list with specified indices using predicate:

swap(List, index1, index2).

I tried this way:

change_value([X|List], 0, Y, [Y|List2]) :- 
        copy_rest([X|List], List2). 
change_value([], P, Y, []).   
change_value([X|List], Pos, Y, [X|List2]) :- 
        X \== Y, 
        Pos > 0, 
        NewPos is Pos - 1, 
        change_value(List, NewPos, Y, List2). 

copy_rest([], []). 
copy_rest([X|List], [X|List2]) :- 
        copy_rest(List, List2).

Is there any better solution?

Thank you very much!

Upvotes: 1

Views: 4695

Answers (2)

brebs
brebs

Reputation: 4438

Using DCG, for performance (due to difference lists):

list_i_j_nth1_swap_using_dcg(I, J, Lst, LstSwap) :-
    integer(I),
    integer(J),
    Min is min(I, J),
    Max is max(I, J),
    Min >= 1,
    Min < Max,
    phrase(list_i_j_nth1_swap(Min, Max), Lst, LstSwap).

list_i_j_nth1_swap(1, Max), [ElemJ] -->
    !, [ElemI], { Max0 is Max - 1 }, list_i_j_nth1_swap_j(Max0, ElemI, ElemJ).
list_i_j_nth1_swap(Min, Max), [E] -->
    [E], { Min0 is Min - 1, Max0 is Max - 1 }, list_i_j_nth1_swap(Min0, Max0).

list_i_j_nth1_swap_j(1, ElemI, ElemJ), [ElemI] --> 
    !, [ElemJ].
list_i_j_nth1_swap_j(Max, ElemI, ElemJ), [E] -->
    [E], { Max0 is Max - 1 }, list_i_j_nth1_swap_j(Max0, ElemI, ElemJ).

Result in swi-prolog:

?- numlist(1, 10, L), time(list_i_j_nth1_swap_using_dcg(2, 4, L, S)).
% 9 inferences, 0.000 CPU in 0.000 seconds (88% CPU, 208792 Lips)
L = [1,2,3,4,5,6,7,8,9,10],
S = [1,4,3,2,5,6,7,8,9,10].

?- time(list_i_j_nth1_swap_using_dcg(2, 9, L, [1,9,3,4,5,6,7,8,2,10])).
% 14 inferences, 0.000 CPU in 0.000 seconds (90% CPU, 272368 Lips)
L = [1,2,3,4,5,6,7,8,9,10].

?- numlist(1, 10000000, L), time(list_i_j_nth1_swap_using_dcg(3, 5, L, S)).
% 10 inferences, 0.000 CPU in 0.000 seconds (86% CPU, 320092 Lips)
S = [1,2,5,4,3,6,7,8,9,10...

?- numlist(1, 10000000, L), time(list_i_j_nth1_swap_using_dcg(2000, 1000, L,
S)).
% 2,005 inferences, 0.319 CPU in 0.325 seconds (98% CPU, 6290 Lips)

Upvotes: 0

repeat
repeat

Reputation: 18726

No need to write recursive code!

Simply use the builtin predicates length/2, same_length/2, and append/3 like so:

list_i_j_swapped(As,I,J,Cs) :-
   same_length(As,Cs),
   append(BeforeI,[AtI|PastI],As),
   append(BeforeI,[AtJ|PastI],Bs),
   append(BeforeJ,[AtJ|PastJ],Bs),
   append(BeforeJ,[AtI|PastJ],Cs),
   length(BeforeI,I),
   length(BeforeJ,J).

Done! Let's put it to use!

?- list_i_j_swapped([e0,e1,e2,e3,e4,e5],5,1,Ys).
  Ys = [e0,e5,e2,e3,e4,e1]
; false.

OK! Does it work in the "other direction", too?

?- list_i_j_swapped(Xs,5,1,[e0,e5,e2,e3,e4,e1]).
  Xs = [e0,e1,e2,e3,e4,e5]
; false.

Alright! What about the following quite general query?

?- list_i_j_swapped([A,B,C],I,J,Ys).
  I = 0, J = 0, Ys = [A,B,C]
; I = 0, J = 1, Ys = [B,A,C]
; I = 0, J = 2, Ys = [C,B,A] 
; I = 1, J = 0, Ys = [B,A,C]
; I = 1, J = 1, Ys = [A,B,C]
; I = 1, J = 2, Ys = [A,C,B]
; I = 2, J = 0, Ys = [C,B,A]
; I = 2, J = 1, Ys = [A,C,B]
; I = J, J = 2, Ys = [A,B,C]
; false.

It worked! At last, we run the most general query:

?- list_i_j_swapped(Xs,I,J,Ys).
  I = 0, J = 0, Xs = [_A]      , Ys = [_A]
; I = 0, J = 0, Xs = [_A,_B]   , Ys = [_A,_B]
; I = 0, J = 1, Xs = [_A,_B]   , Ys = [_B,_A]
; I = 1, J = 0, Xs = [_A,_B]   , Ys = [_B,_A]
; I = 1, J = 1, Xs = [_A,_B]   , Ys = [_A,_B]
; I = 0, J = 0, Xs = [_A,_B,_C], Ys = [_A,_B,_C]
...

Fair enumeration out-of-the-box? What's not to like?

Upvotes: 4

Related Questions