Finding local mins in an array

Question

Is there a easy way to determine the local min and maxes of an array of values. For example

Element Value   Note
1         1 
2         3 
3         5 
4         6 
5         7       max
5         5 
6         4       min
7         6 
8         9 
9         10      max
10        8 
11        7 
12        5      min
13        10    

so an array that is defined like:

let arr = [|1;3;5;6;7;5;4;6;9;10;8;7;5;10|]

would identify

mins  = [|4;5|]

and

maxs  = [|7;10|]

It could be a list or Sequence as well as an array. Two questions

1. Is there any faciliities in F# that that lend themselves to this task
2. Is there a common algorithm for determining either the mins or maxs or both?
3. If writing from scratch should it be approached functionally or imperatively?

Thx

Answer 1

I think it'd be trivial to write

for x from 0 to size-2:
if (a[x] > a[x+1] && a[x+1] < a[x+2]) // also, there should be bound checking
    //a[x+1] is a min!
    minima.cram(x+1)
if (a[x] < a[x+1] && a[x+1] > a[x+2]) // also, there should be bound checking
    //a[x+1] is a max!
    maxima.cram(x+1)

Or have I oversimplified?

Answer 2

This looks like a job for... Seq.windowed! <cue superhero music>

let arr = [|1;3;5;6;7;5;4;6;9;10;8;7;5;10|] 

let _,mins,maxs = 
    arr |> Seq.windowed 3 |> Seq.fold (fun (i,mins,maxs) [|a;b;c|] -> 
    if a>b&&b<c then   (i+1, i::mins,    maxs)
    elif a<b&&b>c then (i+1,    mins, i::maxs)
    else               (i+1,    mins,    maxs)) (1,[],[])

arr |> Seq.iteri (fun i x -> printfn "%2d: %2d" i x)
printfn "mins %A" mins
printfn "maxs %A" maxs
(*
 0:  1
 1:  3
 2:  5
 3:  6
 4:  7
 5:  5
 6:  4
 7:  6
 8:  9
 9: 10
10:  8
11:  7
12:  5
13: 10
mins [12; 6]
maxs [9; 4]
*)

Answer 3

If you're looking for a functional example, you could probably do (in Ruby)

def derivative_signs(list)
  (0..list.length-2).map { |i| (list[i+1] - list[i]) <=> 0 }
  ## <=> is the "rocketship" operator which is basically: be -1 if number is negative
  ##                                                      be 0 if number is zero
  ##                                                      be 1 if number is positive
  ## Alternatively, one could use x / x.abs, with an exception if x == 0
end

def derivative(list)
  (0..list.length-2).map { |i| list[i+1] - list[i] }
end

Coming from calculus, minimums/maximums are when the first derivative changes signs. So one could look through derivative_signs(arr) and find all of the sign changes.

first_derivative_signs = derivative_signs(arr)
# => [1, 1, 1, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1]

Alternatively, you could also do

second_derivative = derivative(derivative_signs(arr))

On the list you provided, you'll get:

[0, 0, 0, -2, 0, 2, 0, 0, -2, 0, 0, 2]

It's clear to see that values with second derivative -2 are maximums, and values with second derivative 2 are minimums. The index of the second derivative is the index of the original list + 1. So the second_derivative[4] that is a -2 corresponds to arr[5] (7), which is a maximum.

Why do we do a "normal" derivative the second time, instead of a derivative_sign?

This is because when a value repeats twice in a row, you'll get unwanted behavior.

For example, consider

[1, 3, 6, 6, 7, 5, 4, 6, 9, 10, 8, 7, 5, 10]
# first_derivative_signs =>  [1, 1, 0, 1, -1, -1, 1, 1, 1, -1, -1, -1, 1]
# second_derivative_signs => [0, -1, 1, -1, 0, 1, 0, 0, -1, 0, 0, 1]
# second_derivative       => [0, -1, 1, -2, 0, 2, 0, 0, -2, 0, 0, 2]

Note that second_derivative_signs throws us some "false" minimums/maximums, while second_derivative, when we check for only -2 and 2, is good.

Answer 4

Based on Brian's answer, I slightly prefer this version:

let arr = [|1;3;5;6;7;5;4;6;9;10;8;7;5;10|] 

let find_min_max input = 
    let windows = Seq.windowed 3 input 
    let mins = Seq.filter (fun [|a;b;c|] -> a>b && b<c) windows
               |> Seq.map (fun [|a;b;c|] -> b)
    let maxs = Seq.filter (fun [|a;b;c|] -> a<b && b>c) windows
               |> Seq.map (fun [|a;b;c|] -> b)

    mins, maxs


let mins, maxs = find_min_max arr 

printfn "mins %A" mins
printfn "maxs %A" maxs

Answer 5

Based on Massif's answer, which is based on Brian's answer, I'd problably roll the filter and map into one:

let find_min_max input =  
    let windows = Seq.windowed 3 input  
    let mins = Seq.choose (fun [|a;b;c|] -> if a>b && b<c then Some(b) else None) windows 
    let maxs = Seq.choose (fun [|a;b;c|] -> if a<b && b>c then Some(b) else None) windows 

    mins, maxs 

:)

Answer 6

I would use Seq.pairwise to get each number and its predecessor. Then you can calculate the difference between each number and its predecessor to get the difference between all values.

In the third step, you go over the differences and look for sign changes. When ever the sign changes, you know that the value before the sign change was an extremum (either min or max).

I don’t know F# at all, but the first step should look like this:

let diffs = Seq.pairwise arr |> Seq.map (-)