Move every second element to the end of the list, recursively

I'm looking for a way to shuffle a list of numbers in a specific way.

shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12])

should return [1, 3, 5, 7, 9, 11, 2, 6, 10, 4, 12, 8]

The recursion will be something like this:

[1,3,5,7,9,11] with remainder [2,4,6,8,10,12]
[2,6,10] with remainder [4,8,12]
[4,12] with remainder [8]

      

and then add lists of results and return the answer you want.

My current code looks like this. How can I adapt it so that it produces the recursion type described above? mode shuffle(+,?)

.

shuffle([], _).
shuffle(List, Shuffled) :- r(List, Shuffled).
r([], []).
r([X], [X]):- !.
r([X,A|Xs], [X|Ys]) :- r(Xs, Ys).

      

+3


source to share


3 answers


First, a predicate that does half the work done: reorders the list so that every second element is selected and added in the opposite direction, preserving the order:

untangle([], []).
untangle([X|Xs], [X|Ys]) :-
    untangle_1([X|Xs], [X|Ys], Bs, Bs).

% The rest of the Untangled is the list at the back;
% the list at the back is now empty
untangle_1([], Back, Back, []).
% Keep elements in odd positions at the front
untangle_1([X|Xs], [X|Untangled], Back, Bs) :-
    untangle_2(Xs, Untangled, Back, Bs).

% Same as above
untangle_2([], Back, Back, []).
% Move elements in even positions to the back
untangle_2([X|Xs], Untangled, Back, [X|Bs]) :-
    untangle_1(Xs, Untangled, Back, Bs).

      

This is very similar to the interwine/3

one defined in this answer . Instead of using two lists for "unpacked" items, it puts them in front and behind the same list.

Now you need to shuffle the elements that would otherwise be attached to the back:



shuffle([], []).
shuffle([X|Xs], Shuffled) :-
    untangle_1([X|Xs], Shuffled, Back, Bs),
    shuffle(Bs, Back).

      

Did I get it right?

?- shuffle([a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z], S), write(S).
[a,c,e,g,i,k,m,o,q,s,u,w,y,b,f,j,n,r,v,z,d,l,t,h,x,p]
S = [a, c, e, g, i, k, m, o, q|...].

      

You will also notice that this one shuffle/2

works in modes shuffle(+List, -Shuffled)

, shuffle(-List, +Shuffled)

and shuffle(?List, ?Shuffled)

. As far as I can see, it is identical in semantics (and almost identical in implementation) to solving false.

+4


source


Here's a version using DCG:

eo([], Ys,Ys) -->
   [].
eo([X|Xs], [X|Ys0],Ys) -->
   eo2(Xs, Ys0,Ys).

eo2([], Ys,Ys) -->
   [].
eo2([X|Xs], Ys0,Ys) -->
   [X],
   eo(Xs, Ys0,Ys).

list_shuffled(Xs, Ys0) :-
    phrase(eo(Xs, Ys0,Ys),Ys). 

      



And here is the most general query showing all the possible uses:

?- list_shuffled(Xs,Ys), numbervars(Xs+Ys,0,_).
Xs = Ys, Ys = [] ;
Xs = Ys, Ys = [A] ;
Xs = Ys, Ys = [A, B] ;
Xs = [A, B, C],
Ys = [A, C, B] ;
Xs = [A, B, C, D],
Ys = [A, C, B, D] ;
Xs = [A, B, C, D, E],
Ys = [A, C, E, B, D] ;
Xs = [A, B, C, D, E, F],
Ys = [A, C, E, B, D, F] ;
Xs = [A, B, C, D, E, F, G],
Ys = [A, C, E, G, B, D, F] ...

      

+2


source


Here's another, somewhat transparent solution using append

:

shuffle([], []).
shuffle([X|T], Shuffled) :-
    unzip([X|T], Odd, Even),
    shuffle(Even, EvenShuffled),
    append(Odd, EvenShuffled, Shuffled).

% Split a list into odd and even elements
unzip([], [], []).
unzip([X], [X], []).
unzip([X,Y|T], [X|Tx], [Y|Ty]) :-
    unzip(T, Tx, Ty).

      

For the record, I prefer Boris and the spurious solutions for this (+1 for both) as both are more efficient. :)

+1


source







All Articles