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

首先，一个完成一半工作的谓词：重新排序列表，以便每隔一个元素被挑选出来并附加到后面，保持顺序：

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 的解决方案。

于 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 回答