遞歸地將每個第二個元素移到列表的後面

Question

我正在尋找一種方法來以特定方式對數字列表進行換位。

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

Answer 1

首先，謂詞得到一半的工作：重新排序列表中，這樣每一個第二個元素挑選出來，並追加到後面，保持順序：

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

這是非常相似到定義爲in this answer的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(+List, -Shuffled)，shuffle(-List, +Shuffled)和shuffle(?List, ?Shuffled)這shuffle/2作品。就我所能看到的而言，它的語義（在實現中幾乎完全相同）與false的解決方案相同。

Answer 2

下面是一個使用版本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] ... 

Answer 3

下面是使用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). 

爲了記錄，我更喜歡Boris和False的解決方案（這兩者都是+1），因爲兩者都更加高效。 :)