在Python中找到数组的转折点

Question

如果我有一个数组：

[3, 5, 7, 9]

A = (0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6)

可以看到有4个转折点。(在A[4]、A[6]、A[13]、A[17])

我该如何使用Python返回转折点的数量?

import numpy as np
import scipy.integrate as SP
import math

def turningpoints(A):
    print A
    N = 0
    delta = 0
    delta_prev = 0
    for i in range(1,19):
        delta = A[i-1]-A[i]       #Change between elements
        if delta < delta_prev:    #if change has gotten smaller
            N = N+1               #number of turning points increases
        delta_prev = delta        #set the change as the previous change
    return N

if __name__ == "__main__":
    A  = np.array([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6])
    print turningpoints(A)

目前，该系统存在缺陷，显然不够优雅。有什么想法吗？

- user2984189

Answer 1

我知道这是一个古老的问题，但我刚遇到了同样的问题，并且正如Cardin在Malvolio的答案评论中所述，该答案无法处理连续值相同的多个转折点，例如[1, 2, 3, 4, 4, 4, 3, 2, 1]。我的实现可以解决这个问题。

虽然它返回两个列表，其中包含最小和最大转折点的索引。

def turning_points(array):
    ''' turning_points(array) -> min_indices, max_indices
    Finds the turning points within an 1D array and returns the indices of the minimum and 
    maximum turning points in two separate lists.
    '''
    idx_max, idx_min = [], []
    if (len(array) < 3): 
        return idx_min, idx_max

    NEUTRAL, RISING, FALLING = range(3)
    def get_state(a, b):
        if a < b: return RISING
        if a > b: return FALLING
        return NEUTRAL

    ps = get_state(array[0], array[1])
    begin = 1
    for i in range(2, len(array)):
        s = get_state(array[i - 1], array[i])
        if s != NEUTRAL:
            if ps != NEUTRAL and ps != s:
                if s == FALLING: 
                    idx_max.append((begin + i - 1) // 2)
                else:
                    idx_min.append((begin + i - 1) // 2)
            begin = i
            ps = s
    return idx_min, idx_max

为了正确回答这个问题，需要计算拐点的数量，具体计算公式如下：

sum(len(x) for x in turning_points(X))

例子

这是一个示例，它展示了一个包含图片的HTML标记。

- Timo

Answer 2

如果您有numpy:

def turningpoints(lst):
    dx = np.diff(lst)
    return np.sum(dx[1:] * dx[:-1] < 0)

或者是不使用 numpy 的等效版本：

def turningpoints(lst):
    dx = [x - y for x, y in zip(lst[1:], lst[:-1])]
    return sum(dx1 * dx2 < 0 for dx1, dx2 in zip(dx[1:], dx[:-1]))

仅仅为了爱好一行代码：

def turningpoints(lst):
    return sum(x0*x1 + x1*x2 < x1*x1 + x0*x2 for x0, x1, x2 in zip(lst[2:], lst[1:-1], lst[:-2]))

但是这个可能会降低可读性 :)

- val

---

第二个错误：TypeError: 'generator' object is not subscriptable。 可能 dx 应该是一个列表。 - rlms

Answer 3

你的想法有些复杂了。 "转折点" 的意思是指比两侧的点要高或低的地方。

def turningpoints(x):
  N=0
  for i in range(1, len(x)-1):
     if ((x[i-1] < x[i] and x[i+1] < x[i]) 
         or (x[i-1] > x[i] and x[i+1] > x[i])):
       N += 1
  return N

>>> turningpoints([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6])
4

- Michael Lorton

---

这个解决方案不起作用。请尝试使用[5, 6, 7, 7, 7, 6, 5]。 - Cardin

@Cardin，你是说这个有两个拐点而不是零吗？那 [5, 6, 7, 7, 7, 8, 9] 呢？它是零个还是两个（或其他什么）？ - Michael Lorton

就是说，这个序列有一个拐点，但是你的算法无法检测到它，因为它假定方向变化必须立即发生。 - Cardin

你新发布的序列没有拐点，因为它是一个静止点。 - Cardin

@Cardin - 我是否错过了官方定义？ - Michael Lorton

正式的转折点是指f'(x) = 0，即方向发生变化的地方吗？我认为它变化的速度并不重要，所以对于像[6,7,7,7,6]这样的序列，它可能仍然被视为一个转折点。但我不是数学家，所以说实话我不确定我的定义有多准确。 - Cardin

Answer 4

>>> def turns(L):
...     answer, delta = 0, -1 if L[1]<L[0] else 1
...     i = 2
...     while i < len(L):
...             d = -1 if L[i]<L[i-1] else 1
...             if d != delta:
...                     answer += 1
...                     delta = d
...             i += 1
...     return answer
... 
>>> L = [0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6]
>>> turns(L)
4

- inspectorG4dget

Answer 5

def group_in_threes(slicable):
    for i in range(len(slicable)-2):
        yield slicable[i:i+3]

def turns(L):
    for index, three in enumerate(group_in_threes(L)):
        if (three[0] > three[1] < three[2]) or (three[0] < three[1] > three[2]):
            yield index + 1

>>> list(turns([0,2,3,4,5,2,1,2,3,4,5,6,7,8,7,6,5,4,5,6]))
[4, 6, 13, 17]
>>> len(_)
4

- rlms