Finding all maximal monotone subsequences in python

Question

Now trying to figure out how to find all the maximal subsequences(both positive and negative) in sequence. Here I got some troubles, because there is no suitable solution found. I've this code, but the output is ok only for positive numbers. I'm newbie to python so can not figure out in short time how can this be handled.

testcase = [1,2,3,4,5,4,3,2,1,0,-1,-2,-3,-2,-1,-2,-1,-2,-3,-4,-5]
def process(lst):
    def sub(lst):
        temp = []
        while lst and (not temp or temp[-1] <= lst[0]):
            temp.append(lst[0])
            lst = lst[1:]
        return temp, lst

    res=[]
    while lst:
        subres, lst = sub(lst)
        res.append(subres[0] if len(subres)==1 else subres) 
    return res
if __name__ == "__main__":
    print(process(testcase))

So, the sample output is

[[1, 2, 3, 4, 5], 4, 3, 2, 1, 0, -1, -2, [-3, -2, -1], [-2, -1], -2, -3, -4, -5]]

While, I want it to be

[[1,2,3,4],[5,4,3,2,1,0,-1,-2,-3],[-2,-1],-2,[-1,-2,-3,-4,-5]]

So, the question is how can this be done?

So, (1) each number is part of exactly one subsequence, and (2) if a number could be part of two, add it to the larger one? — tobias_k, Jul 15 '14 at 13:20
I would recommend [finding all local minimums and maximums](http://stackoverflow.com/questions/4624970/finding-local-maxima-minima-with-numpy-in-a-1d-numpy-array) then splitting sublists from those indexes. — Cory Kramer, Jul 15 '14 at 13:20
Bracketing in your examples seems to be wrong. What are those non-list integers? And shouldn't the `5` be part of the second sequence? — tobias_k, Jul 15 '14 at 13:21
@tobias_k, nice catch. 5 should be included in second list. Non-list integers are elements with length of 1. — im_infamous, Jul 15 '14 at 13:41

loopbackbee · Accepted Answer · 2014-07-15T13:43:41.503

2

You basically need to track the "derivative" (difference between elements), and see when it changes direction.

You can express this very cleanly using numpy:

import numpy as np
np_split_indexes= np.where(np.diff(np.diff(testcase))!=0)[0]+2
split_indexes= [0] + list(np_split_indexes) + [len(testcase)]
result= [testcase[a:b] for a,b in zip(split_indexes[:-1],split_indexes[1:])]

or, if you prefer pure python:

result=[]
tmp=[]
last_direction=0;
last_element=0;
for x in testcase:
    direction= (x-last_element)/abs(x-last_element) #math trick - divide by the magnitude to get the direction (-1/1)
    last_element= x
    if (direction!=last_direction) and tmp:
        result.append(tmp)
        tmp=[]
    last_direction= direction
    tmp.append(x)
if tmp:
    result.append(tmp)

print result

output:

[[1, 2, 3, 4, 5], [4, 3, 2, 1, 0, -1, -2, -3], [-2, -1], [-2], [-1], [-2, -3, -4, -5]]

Note this differs from your intended output on the end. I'm not sure why you grouped -1 in the last group, since it's a local maximum.

edited Jul 15 '14 at 13:43

answered Jul 15 '14 at 13:32

loopbackbee

21,962
10
62
97

Why you split [-2] and [-1] to two separate lists? This looks like [-2, -1] and I can not figure out why the output is different. – im_infamous Jul 15 '14 at 13:47
1

@user3441253 The code relies on finding local minima and maxima - `-2` is a local minimum (local sequence `-1,-2,-1`), and the -1 is a local maximum (local sequence `-2,-1,-2`). . You can later join these subsequences, but note that "maximal monotone sequences" are ambiguous. You could group those as either `[-2, -1], [-2, -1], [-2, -3, -4, -5]` or as `[-2, -1], [-2], [-1, -2, -3, -4, -5]` – loopbackbee Jul 15 '14 at 14:03
Thank you for clarification, I'll keep this in mind. – im_infamous Jul 15 '14 at 16:57

Finding all maximal monotone subsequences in python

1 Answers1