How to shuffle lists in Prolog while preserving inner order

Question

I'm trying to print out all possible shuffled variants of two lists in one list while preserving the order.

I need to write a predicate shuffle(L1, L2, L3) which shuffles L1 and L2 and puts the result into L3 while preserving the inner order of L1 and L2.

For example :

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

What I have so far :

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

This results in :

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

So I'm missing the cases of "simple append" of L1+L2 and L2+L1...

What is my predicate missing?

Answer 1

We can use dcg for its ease of writing:

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

We either take first card from one non-empty deck or the other, but if one of them is empty we must use all the remaining cards in the non-empty deck at once.

Unfortunately this leaves one extra choice point at the end:

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.

As for your approach the problem with it was that you tried to take care of two cards at once, and it got complicated. Going by smallest steps can be the easiest.