Search for local minutes in an array

Question

Is there an easy way to determine the local minimum and maximum values ​​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 

therefore an array that is defined as:

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

will identify

 mins = [|4;5|] 

and

 maxs = [|7;10|] 

This can be a list or sequence, as well as an array. Two questions

• Are there any functions in F # that lend themselves to this task.
• Is there a general algorithm for determining minutes or max or both?
• If you write from scratch, is it necessary to approach functionally or imperatively?

thanks

Answer 1

It looks like work 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 ix -> printfn "%2d: %2d" ix) 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 2

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 3

Based on Massif's answer, which is based on Brian's answer, I probably upset the filter and translated it 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 4

I think it would 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 am I simplified?

Answer 5

If you are looking for a functional example, you can 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 

Based on the calculus, minima / maxima are when the first derivative changes signs. Thus, you can look at derivative_signs(arr) and find all sign changes.

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

Alternatively you can also do

 second_derivative = derivative(derivative_signs(arr)) 

In the list that you indicated, you will receive:

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

It is clear that values ​​with the second derivative -2 are highs, and values ​​with the second derivative 2 are lows. The index of the second derivative is the index of the original list + 1. Thus, second_derivative[4] , that is, -2 , corresponds to arr[5] (7), which is the maximum.

Why do we make a “normal” derivative a second time, instead of the derivative_sign?

This is because when a value is repeated twice in a row, you 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 gives us some “false” minima / maxima, and second_derivative when we check only -2 and 2 is fine.

Answer 6

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

In the third step, you move on to the differences and look at the sign changes. When a sign changes, you know that the value before the sign change was an extremum (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 (-)