How do you split a list into monotonically increasing/decreasing lists?

user_3124438 0
Viewed 345

I have python list that contains several monotonically decreasing elements. However, all these sequences are not adjacent to each other A = [[100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76, 59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8]

I want to extract a1 = [100, 83, 82, 51, 45, 29], a2=[100, 100, 88, 88, 76, 76, 76, 59, 10], a3=[100, 100, 86, 81, 79, 65, 65, 9] from A . As you must have noted that I discarded 12,36,10,8 from A as these do not follow any pattern. The First element of each subarray should be greater than 80. Hence, I have discarded monotonic sub-array with 10 as initial element So far I have this .

def chop_array(array):
    itr = 0
    prev_element = 1e6
    window = list()
    mainWindow = list ()
    for i, element in enumerate(array):
        if element <= prev_element:
            window.append(element)
            prev_element = element
        else:
            mainWindow.append(window)
            prev_element = element
            window = list()
            window.append(element)
    filter_array = [True if item[0] > 80  else False for  item in mainWindow]
    return list(itertools.compress(mainWindow,filter_array))

Is there more efficient way to do it in python ?

python-3.x list numpy python
2 Answers

The starting entry of each sublist can be detected by looking at the locations where difference to previous one is positive. Then we can split the array over these locations; but since np.diff shrinks the array size by 1, we add 1 to the output to get indices with respect to original array:

>>> sub_lists = np.split(A, np.where(np.diff(A) > 0)[0] + 1)
>>> sub_lists

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([12]),
 array([36]),
 array([100, 100,  86,  81,  79,  65,  65,   9]),
 array([10,  8])]

Two kind of filtering needs to be done over this list of arrays: first is to discard any list with 1 item and second is to discard those whose first entry is less than 80. Therefore,

>>> result = [sub for sub in sub_lists if sub.size > 1 and sub[0] > 80]
>>> result

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([100, 100,  86,  81,  79,  65,  65,   9])]

We can wrap these in a function:

def split_decreasing(arr, thre=80):
    """
    Splits the given array `arr` into monotonically decreasing subarrays
    of size at least 2 and first entries being at least `thre`.
    """
    split_points = np.where(np.diff(arr) > 0)[0] + 1
    sub_lists = np.split(arr, split_points)
    result = [sub for sub in sub_lists if sub.size > 1 and sub[0] > thre]
    return result

Sample runs:

>>> split_decreasing([63, 44, 43, 37, 30, 30, 27, 95, 91, 70, 65, 62, 62, 56, 56])

[array([95, 91, 70, 65, 62, 62, 56, 56])]

>>> split_decreasing(np.arange(10))
[]

>>> split_decreasing([12, 11, 7, 9, 7], thre=80)
[]

>>> split_decreasing([12, 11, 7, 9, 7], thre=10)
[array([12, 11,  7])]

>>> split_decreasing([12, 11, 7, 9, 7], thre=5)
[array([12, 11,  7]), array([9, 7])]

>>> split_decreasing([100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76,
                      59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8])

[array([100,  83,  82,  51,  45,  29]),
 array([100, 100,  88,  88,  76,  76,  76,  59,  10]),
 array([100, 100,  86,  81,  79,  65,  65,   9])]
user_93321870

There's a way to solve this by treating it like a Queue, because the next record according to the index is essentially what we want to compare to the others. The added benefit to this method, is you're removing the record and reallocating it. Thus, you're not doubling what you have in memory here.

The one thing I'd mention is that using a list to store the resulting lists is going to be a quick solution to saving the progress as you go.

A = [100, 83, 82, 51, 45, 29, 100, 100, 88, 88, 76, 76, 76, 59, 10, 12, 36, 100, 100, 86, 81, 79, 65, 65, 9, 10, 8]

result = [] # list of lists
r = [] # initialize the logic
r.append(A.pop(0))
while len(A) > 0:
    try:
        # pop the next value
        v = A.pop(0)

        # if its the first value of a sublist, or if its less than the previous record but greater than the next:
        # then add it to the sublist
        if r == [] or (r[-1] >= v and v >= A[0]):
            r.append(v)
        else:
            r.append(v)
            if len(r) > 2:
                result.append(r)
            r = [] # reset the list
    
    # end of the big list, no A[1] to find
    except IndexError as e:
        # add the last one to the r list
        if r[-1] >= v:
            r.append(v)
            if len(r) > 2:
                result.append(r)
        print('reached End of List')
print(result)
user_138801550
Related