Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

create circled List in Prolog

I'm trying to create this function in Prolog:

% Signature: circleList(L1, L2)/2
% Purpose: L2 is a "circled" L1 list.
% Precondition: L1 is fully instantiated.
% Examples:
% ?- circleList([2, 3, 4, 5], X).
% X = [2, 3, 4, 5];
% X = [3, 4, 5, 2];
% X = [4, 5, 2, 3];
% X = [5, 2, 3, 4];
% false.

so i did this:

circleList([],[]).
circleList(X,X).
circleList([H|T],R):- append(T,[H],S), circleList(S,R).

but the output is this:

X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] ;
X = [4, 5, 2, 3] ;
X = [5, 2, 3, 4] ;
X = [2, 3, 4, 5] ;
X = [3, 4, 5, 2] 
and so on...

this is good but i want to make it stop after the first time i'm doing the whole possibilities.

what can i do?

like image 735
kitsuneFox Avatar asked Feb 13 '23 18:02

kitsuneFox


2 Answers

You need another argument to your predicate. One option is to consume the elements in your list until you are left with [].

circleList([Head|Tail],CL):-
    circleList(Tail,[Head],CL).

circleList([],L,L).
circleList([Head|Tail], Rest, CL):-
    append(Rest, [Head], NewRest),
    circleList(Tail, NewRest, CL).
circleList([Head|Tail], Rest, CL):-
    append([Head|Tail], Rest,CL).

Another option I see is limiting the depth to the size of the list using length/2.

circleList([],[]).
circleList(List,CL):-
    length(List, N),
    circleList(List,N,CL).

circleList(_,0,_):-!, fail.
circleList(List,_,List).
circleList([Head|Tail], N, CL):-
    append(Tail, [Head], NewList),
    N1 is N - 1,
    circleList(NewList, N1, CL).
like image 119
Tudor Berariu Avatar answered Feb 16 '23 04:02

Tudor Berariu


You might simply formulate the problem differently:

rotatelist([], []).
rotatelist(Xs, Ys) :-
   Xs = [_|_],
   Ys = [_|_],
   same_length(Xs, Ys), % avoid non-termination
   Bs = [_|_],          % avoid redundant answers
   append(As,Bs,Xs),
   append(Bs,As,Ys).

same_length([], []).
same_length([_E|Es], [_F|Fs]) :-
   same_length(Es, Fs).

But if your point is to explicitly stop ; well, that can easily turn out to be incorrect. In fact, I do not see a natural way how a cut might be used here.

You might, however, limit the number of recursions like so:

circleList2(Xs, Ys) :-
   same_length(Xs, Ys),
   circleList2(Xs, Ys, Xs).

circleList2(X,X, _).
circleList2([H|T],R, [_|L]):-
   L = [_|_],
   append(T,[H],S),
   circleList2(S,R, L).

So this is essentially your program with one additional argument used to limit the number of recursions. Limiting recursion in such a manner is commonly used to implement so called iterative deepening algorithms. In this case, however, we had a single depth bound. No extra iteration was necessary.

like image 34
false Avatar answered Feb 16 '23 02:02

false