Переместить каждый второй элемент в конец списка, рекурсивно

Я ищу способ перетасовать список чисел определенным образом.

shuffle([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]) должен вернуться [1, 3, 5, 7, 9, 11, 2, 6, 10, 4, 12, 8]

Рекурсия будет примерно такой:

[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]

а затем вы добавляете списки результатов и возвращаете требуемый ответ.

Мой текущий код выглядит следующим образом. Как я могу приспособить это так, чтобы это произвело тип рекурсии, который я объяснил выше? режим shuffle(+,?),

shuffle([], _).
shuffle(List, Shuffled) :- r(List, Shuffled).
r([], []).
r([X], [X]):- !.
r([X,A|Xs], [X|Ys]) :- r(Xs, Ys).
Источник

3 ответа

Решение

Во-первых, предикат, который выполняет половину работы: переупорядочивает список так, чтобы каждый второй элемент выбирался и добавлялся в конец, сохраняя порядок:

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

Это очень похоже на interwine/3 определено в этом ответе. Вместо использования двух списков для "разархивированных" элементов, он помещает их в начало и конец того же списка.

Теперь вам нужно перетасовать элементы, которые в противном случае были бы добавлены в конец:

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

Я правильно понял?

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

Вы также заметите, что это shuffle/2 работает в режимах shuffle(+List, -Shuffled), shuffle(-List, +Shuffled), а также shuffle(?List, ?Shuffled), То, что я вижу, идентично по семантике (и почти идентично по реализации) решению false.

Источник

Вот версия с использованием 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).

И вот самый общий запрос, показывающий все возможные варианты использования:

?- 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] ...
Источник

Вот еще одно, несколько прозрачное решение, использующее 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).

Для справки, я предпочитаю решения Бориса и Ложи этому (+1 к обоим), так как оба более эффективны.:)

Источник
Другие вопросы по тегам