Local Maxima
February 16, 2021
We keep track of both the previous element and the current direction, either climbing up or falling down, and compute the maxima in a single scan of the list:
(define (lmax xs)
(if (null? xs) (error 'lmax "empty")
(let loop ((xs (cdr xs)) (prev (car xs)) (dir 'up) (maxs (list)))
(cond ((null? xs)
(reverse (if (equal? dir 'up) (cons prev maxs) maxs)))
((= prev (car xs)) (loop (cdr xs) prev dir maxs))
((< prev (car xs)) (loop (cdr xs) (car xs) 'up maxs))
((equal? dir 'up) (loop (cdr xs) (car xs) 'down (cons prev maxs)))
(else (loop (cdr xs) (car xs) 'down maxs))))))
Here is the sample problem:
> (lmax '(1 2 1 2 3 4 3 2 3 2 1)) (2 4 3)
You can run the program at https://ideone.com/RduLyR.
Programming Praxis 
Perl version…
say join ' ', maxima( qw(1 2 1 2 3 4 3 2 3 2 1) ); sub maxima { my @X = @_; push @X, my $left = -1e32; my @sol; while(@X>1) { push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1]; $left = shift @X; } return @sol; }Here’s a solution in Python. It’s not particularly efficient, as it creates multiple copies of the input list.
from itertools import groupby def local_maxima(l): assert len(l) > 0, 'Input can\'t be empty' # Remove adjacent duplicates and add boundary elements l = [l[0] - 1] + [x for x, _ in groupby(l)] + [l[-1] - 1] return [y for x, y, z in zip(l, l[1:], l[2:]) if x < y and y > z] l = [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1] print(local_maxima(l))Output:
Cache version
[sourcecode lang="css"]
test ;
q
;
localmaxima(list) ; Output local maxima
n i,next,previous,this
s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1)
s output=””
f i=2:1:$l(list,” “)-1 {
s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1)
i this>previous, this>next s output=output_this” ”
}
q $e(output,1,$l(output)-1)
Here is a solution in a somewhat functional style using standard R7RS
Scheme and a few well-known helpers form SRFI 1. It provides both
values and locations of the local maxima.
(import (scheme base) (only (srfi 1) circular-list filter-map iota) (scheme write)) (define samples ; ((input . output) ...) '(((1 2 1 2 3 4 3 2 3 2 1) . (1 5 8)) (() . ()) ((1) . (0)) ((1 1) . (0)) ((7 7 7) . (0)) ((7 6 7) . (0 2)) ((7 7 6 7) . (0 3)) ((7 7 7 7 6 7) . (0 5)) ((7 7 7 7 6 7 7) . (0 5)) ((7 7 5 5 6 7 7 6 7 5 7) . (0 5 8 10)) ((7 7 5 5 6 7 7 6 7 5 7 7) . (0 5 8 10)) ((7 7 5 5 6 7 7 6 7 5 7 6) . (0 5 8 10)))) ;; nums -> ((lmax-val lmax-idx) ...) (define (local-maxima nums) (let* ((xs (apply circular-list -inf.0 nums)) (ys (cdr xs)) (zs (cdr ys)) (yi (iota (length nums)))) ;; x, y, z are consecutive nums with -inf.0 as sentinel at both ends (filter-map (lambda (x y z i) ;; is y a local maximum, leftmost in case of plateau? (and (< x y) (<= z y) (list y i))) xs ys zs yi))) (define (local-maxima-values nums) (map car (local-maxima nums))) (define (local-maxima-indexes nums) (map cadr (local-maxima nums))) (define (demo) (display (equal? (map cdr samples) (map local-maxima-indexes (map car samples)))) (newline)) (demo)Output:
Cache version – Fix formatting
test ; q ; localmaxima(list) ; Output local maxima n i,next,previous,this s list=$e(list)-1_” “list” “($e(list,$l(list)-1)-1) s output=”” f i=2:1:$l(list,” “)-1 { s this=$p(list,” “,i),previous=$p(list,” “,i-1),next=$p(list,” “,i+1) i this>previous, this>next s output=output_this” ” } q $e(output,1,$l(output)-1)s list=”1 2 1 2 3 4 3 2 3 2 1″
w !,list,!,$$localmaxima(list)
1 2 1 2 3 4 3 2 3 2 1
2 4 3
@James Curtis-Smith
I’m unfamiliar with Perl. I tried typing your program into a file and executing it:
$ perl -e localmaxima.pl
Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
$ perl -E localmaxima.pl
Steve@DESKTOP-0SFLH1S MINGW64 ~/Desktop
$ perl localmaxima.pl
syntax error at localmaxima.pl line 1, near “say join”
Execution of localmaxima.pl aborted due to compilation errors.
I also tried typing it into the interpreter, but couldn’t figure out how to execute it.
Any tips?
Thanks, Steve
Changed the program (localmaxima.pl) to the following, and executing “./localmaxima.pl” returned the expected values:
#!/usr/bin/perl
print join ‘ ‘, maxima( qw(1 2 1 2 3 4 3 2 3 2 1) );
sub maxima {
my @X = @_;
push @X, my $left = -1e32;
my @sol;
while(@X>1) {
push @sol,$X[0] if $left < $X[0] && $X[0] > $X[1];
$left = shift @X;
}
return @sol;
}
Sure enjoy learning new languages and seeing new solutions.
Thanks, all.
Steve
@James Curtis-Smith and @bookofstevegraham: What do your programs return when given (1 3 3 1) as input? They should return a local maximum of (3).
@programmingpraxis: Good catch – Didn’t know you read Cache/Mumps! I was allowing for mountain peaks as maxima, but not buttes.
Revised program and tests
>zl test zp s qt="""" for list="1 2 1 2 3 4 3 2 3 2 1","1 3 3 1","","1","1 1","7 7 7","7 6 7","7 7 6 7","7 7 7 7 6 7","7 7 7 7 6 7 7","7 7 5 5 6 7 7 6 7 5 7","7 7 5 5 6 7 7 6 7 5 7 7", "7 7 5 5 6 7 7 6 7 5 7 6" w !!,qt,list,qt,!,qt,$$localmaxima^test(list),qt test ; q ; localmaxima(list) ; Output local maxima n i,next,previous,this s list=$e(list)-1_" "_list_" "_($e(list,$l(list)-1)-1),output="" f i=2:1:$l(list," ")-1 { s this=$p(list," ",i),previous=$p(list," ",i-1),next=$p(list," ",i+1) i this>previous,this'<next s output=output_this_" " } q $e(output,1,$l(output)-1)“1 2 1 2 3 4 3 2 3 2 1”
“2 4 3”
“1 3 3 1”
“3”
“”
“”
“1”
“1”
“1 1”
“1”
“7 7 7”
“7”
“7 6 7”
“7 7”
“7 7 6 7”
“7 7”
“7 7 7 7 6 7”
“7 7”
“7 7 7 7 6 7 7”
“7 7”
“7 7 5 5 6 7 7 6 7 5 7”
“7 7 7 7”
“7 7 5 5 6 7 7 6 7 5 7 7”
“7 7 7 7”
“7 7 5 5 6 7 7 6 7 5 7 6”
“7 7 7 7”
@bookofstevegraham: Actually, I don’t speak cache/mumps. but it’s not too hard to figure out that you have a statement “if this > previous and this > next then output this” which handles peaks but not plateaus.
The problem is my fault, not yours. The description mentions plateaus, but not clearly, and I didn’t give an example of an input that contains plateaus. If my example had been (1 2 1 2 3 4 3 2 3 3 3 2 1) the situation would have been obvious.
@programmingpraxis: Good points. Thanks for your efforts: They have provided many hours of enjoyment and learning.
Here’s a Haskell version. We take advantage of
Nothingbeing less thanJust xfor allx(assumingxis comparable). Also, the functiondivvyis such thatdivvy 3 1 [1..5]equals[[1,2,3],[2,3,4],[3,4,5]].import Data.List (group) import Data.List.Split (divvy) import Data.Maybe (mapMaybe) locmax :: Ord a => [a] -> [a] locmax xs = map head $ group $ mapMaybe midMax $ divvy 3 1 ys where ys = [Nothing] ++ map Just xs ++ [Nothing] midMax [x, y, z] = if x <= y && y >= z then y else Nothing main :: IO () main = do print $ locmax ([] :: [()]) print $ locmax [5] print $ locmax [5, 4] print $ locmax [5, 6] print $ locmax [5, 5, 5, 6, 6] print $ locmax [1, 2, 1, 2, 3, 4, 3, 2, 3, 2, 1]A solution in Racket:
;e: local maxima to be indicated in square brackets like so: (1 [2] 1 2 3 [4] 3 2 [3] 2 1) (define (loc-max input) (foldl (λ (val init) (let ((last (car init)) (next (if (null? (cdadr init)) null (cadadr init)))) (let ((tmp (if (and (or (null? last) (<= last val)) (or (null? next) (< next val))) "[~a]" "~a"))) (list val (cdadr init) (cons (format tmp val) (caddr init)))))) (list null input null) input)) (define (local-maxima input) (display (string-join (reverse (caddr (loc-max input))) #:before-first "(" #:after-last ")")))Examples: