Нахождение локальных минут в массиве

Question

Есть ли простой способ определить локальные минимумы и максимумы массива значений.Например,

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    

, поэтому массив, определенный как:

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

, будет идентифицировать

mins  = [|4;5|]

и

maxs  = [|7;10|]

Itможет быть список или последовательность, а также массив.Два вопроса

1. Есть ли в F # какие-либо возможности, которые пригодны для этой задачи
2. Существует ли общий алгоритм для определения минимума или максимума или обоих?
3. Если писать с нуля, следует ли к нему подходить функционально или обязательно?

Thx

Answer 1

Это похоже на работу для ... 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]
*)

Answer 2

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

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 3

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

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 4

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

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)

Или я слишком упрощен?

Answer 5

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

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

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

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

Answer 6

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