prolog - 如何在 Prolog 中打乱列表同时保留内部顺序

Question

我试图在一个列表中打印出两个列表的所有可能的打乱变体，同时保留顺序。

我需要编写一个谓词 shuffle(L1, L2, L3) 来对 L1 和 L2 并将结果放入 L3，同时保留 L1 和 L2 的内部顺序。

例如:

?- shuffle([a,b],[1,2],L).
L = [a,b,1,2] ;
L = [a,1,b,2] ;
L = [a,1,2,b] ;
L = [1,a,b,2] ;
L = [1,a,2,b] ;
L = [1,2,a,b]

到目前为止我所拥有的:

shuffle([],[],[]).
shuffle([X|Xs],[Y|Ys],[X,Y|Tail]) :-
    shuffle(Xs,Ys,Tail).
shuffle([X|Xs],[Y|Ys],[Y,X|Tail]) :-
    shuffle(Xs,Ys,Tail).

这会导致:

| ?- shuffle([a,b],[1,2],L).
L = [a,1,b,2] ? ;
L = [a,1,2,b] ? ;
L = [1,a,b,2] ? ;
L = [1,a,2,b]

所以我错过了L1+L2和L2+L1的“简单追加”情况...

我的谓词缺少什么？

Answer 1

我们可以使用dcg为了便于书写:

shuffle([A|B],[C|D]) --> [A] , shuffle(B,[C|D]). 
shuffle([A|B],[C|D]) --> [C] , shuffle([A|B],D).
shuffle(A,[]) --> A.
shuffle([],C) --> C.

shuffle( A, B, C) :- phrase( shuffle(A,B), C).

我们要么从一个非空牌组或另一个中取出第一张牌，但如果其中一张是空的，我们必须立即使用非空牌组中的所有剩余牌。

不幸的是，这在最后留下了一个额外的选择点:

5 ?- shuffle([a,b],[1,2],C).
C = [a, b, 1, 2] ;
C = [a, 1, b, 2] ;
C = [a, 1, 2, b] ;
C = [1, a, b, 2] ;
C = [1, a, 2, b] ;
C = [1, 2, a, b] ;
false.

至于你的方法，问题在于你试图同时处理两张牌，结果变得很复杂。采取最小的步骤可能是最简单的。