CODEWITHSUNDEEP
listrotationprolog
Dave
Dave

Reputation: 473

Find all list rotations in Prolog

I'm trying to produe all possible list rotations in Prolog. Here is an example:

rotate([1,2,3], X).
X = [1,2,3];
X = [2,3,1];
X = [3,1,2].

I found a way to make one rotation:

rotate([H|T], R) :-
    append(T, [H], R).

But how to find all?

Answer

rotate(L, R) :-
    append(Left, Right, L),
    append(Right, Left, R),
    Right \= [].

Upvotes: 3

Views: 341

Answers (1)

Paulo Moura
Paulo Moura

Reputation: 18683

You can use the append/3 predicate to split a list into a prefix and a suffix. For example:

?- append(Prefix, Suffix, [1,2,3]).
Prefix = [],
Suffix = [1, 2, 3] ;
Prefix = [1],
Suffix = [2, 3] ;
Prefix = [1, 2],
Suffix = [3] ;
Prefix = [1, 2, 3],
Suffix = [] ;
false.

Then, appending a suffix to a prefix gives you a rotation:

| ?- append(_Prefix, _Suffix, [1,2,3]), append(_Suffix, _Prefix, Rotation).

Rotation = [1,2,3] ? ;
Rotation = [2,3,1] ? ;
Rotation = [3,1,2] ? ;
Rotation = [1,2,3]
yes

But there's a redundant solution. Can you get rid of it? Hint: if either prefix or suffix is an empty list, you get the original list.

Upvotes: 4

Related Questions