Поиск локальных минут в массиве

Похоже, это работа для... Seq.windowed! ‹супергеройская музыка>

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]
*)

Основываясь на ответе Брайана, я немного предпочитаю эту версию:

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

Основываясь на ответе Массифа, который основан на ответе Брайана, я бы, вероятно, объединил фильтр и карту в один:

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 

:)

Я думаю, что было бы тривиально написать

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)

Или я упростил?

Если вы ищете функциональный пример, вы, вероятно, могли бы сделать (в 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

Исходя из исчисления, минимумы/максимумы - это когда первая производная меняет знак. Таким образом, можно просмотреть derivative_signs(arr) и найти все изменения знака.

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

В качестве альтернативы вы также можете сделать

second_derivative = derivative(derivative_signs(arr))

В списке, который вы предоставили, вы получите:

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

Ясно видно, что значения со второй производной -2 являются максимальными, а значения со второй производной 2 — минимальными. Индекс второй производной равен индексу исходного списка + 1. Таким образом, second_derivative[4], то есть -2, соответствует arr[5] (7), что является максимумом.

Почему мы делаем «нормальную» производную во второй раз вместо производной_знака?

Это связано с тем, что когда значение повторяется дважды подряд, вы получите нежелательное поведение.

Например, рассмотрим

[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]

Обратите внимание, что second_derivative_signs выдает нам несколько "ложных" минимумов/максимумов, в то время как second_derivative, когда мы проверяем только -2 и 2, является хорошим.

Я бы использовал Seq.pairwise для получения каждого числа и его предшественника. Затем вы можете вычислить разницу между каждым числом и его предшественником, чтобы получить разницу между всеми значениями.

На третьем этапе вы просматриваете различия и ищете изменения знаков. Когда знак меняется, вы знаете, что значение до изменения знака было экстремумом (либо минимальным, либо максимальным).

Я совсем не знаю F#, но первый шаг должен выглядеть так:

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