CODEWITHSUNDEEP
pythonlist
im_infamous
im_infamous

Reputation: 1062

Finding all maximal monotone subsequences in python

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?

Upvotes: 0

Views: 652

Answers (1)

loopbackbee
loopbackbee

Reputation: 23322

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.

Upvotes: 2

Related Questions