Friday, November 3, 2017

Shuffle in prolog

By Hường Hana 8:30 AM prolog Leave a Comment

I'm trying to write a procedure in prolog where if L1 = [1,2,3] and L2 = [4,5,6] then L3 = [1,4,2,5,3,6]

so shuffle([1,2,3],[4,5,6],[1,4,2,5,3,6])

I have this so far:

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

This is my first attempt at writing prolog code so I'm still trying to wrap my head around the syntax, rules and everything.

I understand the logic, I'm just not sure how to implement it so any help would be greatly appreciated!

Thanks!

Edit: I've figured it out. Here's the solution if anyone's interested:

shuffle([X],[Y],[X,Y]).   shuffle([X|Xs],[Y|Ys],[Z1,Z2|Zs]) :- shuffle([X],[Y],[Z1,Z2]),shuffle(Xs,Ys,Zs).

2 Answers

shuffle([], B, B). shuffle([H|A], B, [H|S]) :- shuffle(B, A, S).

In this kind of problems, usually the difficult part is not Prolog but identifying the simplest recursive relation that solves it.

Here's the simple solution:

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

Generalizing this to handle list of unequal length is a matter of changing the base case into:

shuffle(Xs, [], Xs). shuffle([], Ys, Ys).

although that may generate duplicate solutions. Those can be fixed with a cut if you don't mind the predicate being "one-way".

(Though I still think you should call this flatzip or interlace instead of shuffle.)