CODEWITHSUNDEEP
prolog
GoldAK47
GoldAK47

Reputation: 11

prolog: Local maximum in a list

I'm trying to find out the local maximum in a list. Basically I am to find values that are greater than the element before the list and the element after it, and the result should be a list of all the local maximum values.

Example: so a query local_maximum([3,2,3,4,5,2,7,3,6,5], Answer) should answer Answer=[5,7,6] (since 5>4 , 5>2... 7>2, 7>3 and so on..)

My logic is do you keep doing recursive calls until you reach only 3 elements in the list. You check if the middle element is greater than the left and right element, and if it is you add it to the list.

Also, my intention is as I go up the recursive call tree, I always want to check whether the second element in the recursive call tree is greater than the one left and right to it.
i.e 

1,3,5,2,1
|
3,5,2,1
|
5,2,1
BASE CASE
checks if 2 is greater than 5, and 1.... append nothing...
|
3,5,2,1
checks if 5 is greater than 3 and 2, append 5...

so on..

/*base case stop if it reaches 3 elements*/
local_maximum([X,Y,Z], Answer):- Y>X, Y>Z, Answer is Y. 
local_maximum([X,Y,Z], []):- Y<X, Y<Z.

local_maximum([H|T], Answer):-
local_maximum(T, Answer), append([], Answer, Answer).

I don't know how to go about on this... sorry for my english. regards,

Solved.

You can check while you visit the list, and save just elements that fits:

local_maximum([X,Y,Z|Xs], [Y|Ms]) :-
Y>X, Y>Z,
local_maximum([Z|Xs], Ms).

then add the skip and the base case rules. The way you write the skip case will influence the rule above, requiring a cut placed here. This because Prolog will search alternatives on request! I think that the added cut improves readability of the 'program'.

Upvotes: 1

Views: 938

Answers (2)

Michael
Michael

Reputation: 1

I don't know about the previous solution but after attempting this problem myself this is how I was able to solve it.

local_maximum([X,Y,Z], [Y|Ms]):-
  nonvar(X), nonvar(Y), nonvar(Z),
  Y>X, Y>Z, !.

local_maximum([X,Y,Z|Xs], [Y|Ms]):-
  nonvar(X), nonvar(Y), nonvar(Z),
  Y>X, Y>Z,
  local_maximum([X,Z|Xs], Ms).

local_maximum([X,Y,Z|Xs], Ms):-
  nonvar(X), nonvar(Y), nonvar(Z),
  local_maximum([X,Z|Xs], Ms), !.

So by testing it you will get.

| ?- local_maximum([3,2,3,4,5,2,7,3,6,5], Y).
Y = [5,7,6|_]

Upvotes: 0

CapelliC
CapelliC

Reputation: 60034

you can check while you visit the list, and save just elements that fits:

local_maximum([X,Y,Z|Xs], [Y|Ms]) :-
  Y>X, Y>Z,
  local_maximum([Z|Xs], Ms).

then add the skip and the base case rules. The way you write the skip case will influence the rule above, requiring a cut placed here. This because Prolog will search alternatives on request! I think that the added cut improves readability of the 'program'.

I tested the version with the cut:

?- local_maximum([3,2,3,4,5,2,7,3,6,5], Answer).
Answer = [5, 7, 6].

?- local_maximum([1,2,1,2,1], Answer).
Answer = [2, 2].

Upvotes: 2

Related Questions