Prolog recursive list shuffling

0
votes

Revising for a prolog exam and working through past papers that we don't have answers for and I've got stuck halfway through a problem and I was really hoping for some help!

The question: Write a predicate permute(Xs, Ys) that scrambles the elements of the list Xs to obtain the scrambled list Ys.

The query ?- permute([1,2,3], Ys). should succeed six times and give the following answers:

Ys = [1,2,3]
Ys = [2,1,3]
Ys = [2,3,1]
Ys = [1,3,2]
Ys = [3,1,2]
Ys = [3,2,1]

though not necessarily in that order.

We're advised to use a predicate we've already made, and so far I have this:

insert([], Y, [Y]).
insert([H|T], Y, [Y, H|T]).
insert([H|T], Y, [H|T2]) :- insert(T, Y, T2).

permute([], []).
permute([H|T], X) :- insert(T, H, X).

When I query it I only get half as many as I should, and I can't work out to switch the order of the list.

?- permute([1,2,3], Ys).
Ys = [1,2,3],
Ys = [2,1,3],
Ys = [2,3,1].

Any advice greatly appreciated!

1
prolog
You might find this answer useful. - Daniel Lyons
@DanielLyons thank you that has helped some, and if I run perm([1,2,3], P) of the code in the answer it works, but I'm really struggling to "translate" (for want of a better word) the select/3 predicate into my insert/3 predicate which I have to use - user9759943
Don't think of predicates as functions. Predicates define relationships between arguments. So insert/3 and select/3 are completely equivalent to each other, just with re-arrangement of arguments. - lurker
@lurker really sorry if I'm being obtuse, but if the select/3 in perm(List, [First|Perm]) :- select(First, List, Rest), perm(Rest, Perm). is the same as my insert/3, I just can't work out what the recursive call would be. I've trued rearranging and matching the arguments and failed miserably - user9759943
Did you test your insert/3 predicate on its own, independent of permute/2? If so, does it work correctly? My other comment was just that: insert(ListWithoutX, X, ListWithX) is the same as select(X, ListWithX, ListWithoutX) (as defined in the Prolog library). If properly implemented, their behavior should be the same. - lurker

1 Answers

0
votes

Just for fun, here's a solution entirely based on append/3:

permute(XX, [B|YY]) :-
    append(AA,[B|CC],XX),  % remove random element B from XX
    append(AA,CC,DD),      % DD is XX without B
    permute(DD,YY).        % permute DD into YY
permute([],[]).

Simple to understand, but probably less efficient than the traditional implementation (altough the operating principle is exactly the same; read the comments) that has been already suggested.