CODEWITHSUNDEEP
prolog
Daniel Lewinski
Daniel Lewinski

Reputation: 25

How to shuffle lists in Prolog while preserving inner order

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?

Upvotes: 2

Views: 345

Answers (4)

brebs
brebs

Reputation: 4456

@repeat's answer is more elegant and efficient, but, as an alternative:

The unwanted choice-point can be removed using a reusable empty_list_first predicate:

shuffle([A|B], [C|D]) --> [A],
    shuffle(B, [C|D]).
shuffle([A|B], [C|D]) --> [C],
    { empty_list_first([A|B], D, A1, D1) },
    shuffle(A1, D1).

% Rewritten to prevent needing https://www.swi-prolog.org/pldoc/man?section=basics
%shuffle([], C) --> remainder(C).
shuffle([], C, C, []).

shuffle(A, B, C) :-
    empty_list_first(A, B, A1, B1),
    phrase(shuffle(A1, B1), C).

empty_list_first([], L2, [], L2).
empty_list_first([H|T], L2, EL1, EL2) :-
    empty_list_first_(L2, [H|T], EL1, EL2).

empty_list_first_([], L1, [], L1).
% If neither are empty, keep original order
empty_list_first_([H|T], L1, L1, [H|T]).

Result in swi-prolog:

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

Upvotes: 1

repeat
repeat

Reputation: 18726

Here's how you can shuffle two lists while preserving the relative item order.

shuffle([], Xs, Xs).
shuffle([X|Xs], Ys, Zs) :-
   shuffle_(Ys, X, Xs, Zs).          % use auxiliary predicate shuffle_/4

shuffle_([], X, Xs, [X|Xs]).         % do indexing on both lists
shuffle_([Y|Ys], X, Xs, [X|Zs]) :-
   shuffle_(Xs, Y, Ys, Zs).
shuffle_([Y|Ys], X, Xs, [Y|Zs]) :-
   shuffle_(Ys, X, Xs, Zs).

Sample query using SWI-Prolog:

?- shuffle([a,b], [1,2], Xs).
   Xs = [a,1,b,2]
;  Xs = [a,1,2,b]
;  Xs = [a,b,1,2]
;  Xs = [1,a,2,b]
;  Xs = [1,a,b,2]
;  Xs = [1,2,a,b].                   % no useless choice point at the end

Upvotes: 2

ronle
ronle

Reputation: 129

My answer is posted long time after original question but hoping this might prove useful to someone some day. I've taken a different approach to this, might be on the longer side but it works... :) Since one of the requirements at the class I'm taking to not exceed material learned, some items such as delete and concatenate have been created here as well.

del(X,[X|Xs],Xs).
del(X,[Y|Ys],[Y|Zs]):-
    del(X,Ys,Zs).

permutation([],[]).
permutation(Xs,[Z|Zs]):-
    del(Z,Xs,Ys),
permutation(Ys,Zs).

conc([],L,L).
conc([X|L1],L2,[X|L3]):-
    conc(L1,L2,L3).

is_in_order([],_).
is_in_order([_],_).
is_in_order(Sublist1, Sublist2, Superlist) :-
    remove_elements(Superlist, Sublist1, SuperSubList),
    list_equal(Sublist2, SuperSubList).

list_equal([], []).
list_equal([X|Xs],[X|Ys]) :-
    list_equal(Xs, Ys).

% Remove L1 from L2 and return the resulting list
remove_elements(L, [H|T], R) :-
    delete(L, H, R1),
    remove_elements(R1, T, R).
remove_elements(L, [], L).

/*Shuffle first creates a concatenated list from both L1 & L2
 * It then create permutation for all possible combinations of L1 & L2
 * Once done, it scrubs the new lists to filter out the ones that do not 
 * maintain the original order of L1 & L2
 * The result is only the permutations that fullfills the order condition
*/

shuffle(L1,L2,L):-
    conc(L1,L2,L3),
    permutation(L3, L),
    is_in_order(L1, L2, L),
    is_in_order(L2, L1, L).

Upvotes: 0

Will Ness
Will Ness

Reputation: 71109

We can use 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.

Upvotes: 2

Related Questions