3

特定の方法で数字のリストをシャッフルする方法を探しています。

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

3 に答える 3

4

まず、作業の半分を完了する述語: リストを並べ替えて、2 つおきの要素が選択されて後ろに追加されるようにし、順序を維持します。

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で定義されているものと非常によく似ています。「解凍された」要素に 2 つのリストを使用する代わりに、それらを同じリストの前後に配置します。

ここで必要なのは、そうでなければ後ろに追加される要素をシャッフルすることです:

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 のソリューションとセマンティクスが同じです (実装もほぼ同じです)。

于 2014-10-02T14:18:22.410 に答える
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] ...
于 2014-10-02T15:01:21.510 に答える
1

を使用した別のやや透過的なソリューションを次に示し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)。どちらもより効率的です。:)

于 2014-10-02T16:44:40.057 に答える