Finding turning points of an Array in python

Question

If I for example have an array:

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

It can be seen that there are 4 turning points. (at A[4],A[6], A[13], A[17])

How can I use python to return the number of turning points?

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)

Currently, this system is flawed and certainly not very elegant. Any ideas?

score 7 · Answer 1 · answered Nov 12 '13 at 17:51

If you have numpy:

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

Or the non-numpy equivalent version:

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

And just for the love of one-liners:

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

But the readability is arguably decreased on this one :)

For the second one: `TypeError: 'generator' object is not subscriptable`. Presumably `dx` should be a list. — rlms, Nov 12 '13 at 17:53

score 7 · Answer 2 · answered Jan 20 '18 at 20:18

I know it's an old question, but I just had the same problem and as Cardin stated in the comments of Malvolio's answer, the answer cannot handle successive points with the same value like [1, 2, 3, 4, 4, 4, 3, 2, 1]. My implementation can handle this problem.

Although, it returns two lists with the indices of the minimum and maximum turning points.

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

To correctly answer the question, the number of turning points is then computed as:

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

Example

score 4 · Accepted Answer · answered Nov 12 '13 at 17:43

4

You're overthinking it. A "turning point" is one that is either higher than the points on both sides, or lower.

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

answered Nov 12 '13 at 17:43

Michael Lorton

43,060
26
103
144

3

This solution doesn't work. Try [5, 6, 7, 7, 7, 6, 5] – Cardin Jan 23 '15 at 08:33
@Cardin, are you saying this has two turning points instead of zero? What about [5, 6, 7, 7, 7, 8, 9]? Does that have zero or two (or something else)? – Michael Lorton Jan 23 '15 at 15:47
As in, that sequence has 1 turning point, but your algorithm fails to detect it, because it assumes that the direction change has to occur immediately. – Cardin Jan 24 '15 at 16:40
Your newly posted sequence doesn't have any turning point, because it's a stationary point instead. – Cardin Jan 24 '15 at 16:46
@Cardin -- is there an official definition I am missing? – Michael Lorton Jan 24 '15 at 17:04
officially turning point => f'(x) = 0 where it changes direction? I don't think how fast it changes direction matters, so for a sequence like [6,7,7,7,6] it probably still counts as a turning point. I'm not a mathematician though, so tbh I'm not sure how accurate my definition is. – Cardin Jan 26 '15 at 00:36

score 1 · Answer 4 · answered Nov 12 '13 at 17:41

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

score 0 · Answer 5 · answered Nov 12 '13 at 17:50

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

Finding turning points of an Array in python

5 Answers5

Example