Find monotonic sequences in a list?

Question

I'm new in Python but basically I want to create sub-groups of element from the list with a double loop, therefore I gonna compare the first element with the next to figure out if I can create these sublist, otherwise I will break the loop inside and I want continue with the last element but in the main loop:

Example: 5,7,8,4,11

Compare 5 with 7, is minor? yes so include in the newlist and with the inside for continue with the next 8, is minor than 5? yes, so include in newlist, but when compare with 4, I break the loop so I want continue in m with these 4 to start with the next, in this case with 11...

for m in xrange(len(path)):
    for i in xrange(m+1,len(path)):
              if (path[i] > path[m]):
                  newlist.append(path[i])

             else:
                  break

             m=m+i

Thanks for suggestions or other ideas to achieve it!

P.S. Some input will be: input: [45,78,120,47,58,50,32,34] output: [45,78,120],[47,58],50,[32,34]

The idea why i want make a double loops due to to compare sub groups of the full list,in other way is while 45 is minor than the next one just add in the new list, if not take the next to compare in this case will be 47 and start to compare with 58.

Answer 1

I used a double loop as well, but put the inner loop in a function:

#!/usr/bin/env python

def process(lst):

    def prefix(lst):
        pre = []
        while lst and (not pre or pre[-1] <= lst[0]):
            pre.append(lst[0])
            lst = lst[1:]
        return pre, lst

    res=[]
    while lst:
        subres, lst = prefix(lst)
        res.append(subres) 
    return res

print process([45,78,120,47,58,50,32,34])
=> [[45, 78, 120], [47, 58], [50], [32, 34]]

The prefix function basically splits a list into 2; the first part is composed of the first ascending numbers, the second is the rest that still needs to be processed (or the empty list, if we are done).

The main function then simply assembles the first parts in a result lists, and hands the rest back to the inner function.

I'm not sure about the single value 50; in your example it's not in a sublist, but in mine it is. If it is a requirement, then change

        res.append(subres) 

to

        res.append(subres[0] if len(subres)==1 else subres)

print process([45,78,120,47,58,50,32,34])
=> [[45, 78, 120], [47, 58], 50, [32, 34]]

Answer 2

No loop! Well at least, no explicit looping...

import itertools

def process(lst):
    # Guard clause against empty lists
    if len(lst) < 1:
        return lst

    # use a dictionary here to work around closure limitations
    state = { 'prev': lst[0], 'n': 0 }

    def grouper(x):
        if x < state['prev']:
            state['n'] += 1

        state['prev'] = x
        return state['n']

    return [ list(g) for k, g in itertools.groupby(lst, grouper) ]

Usage (work both with Python 2 & Python 3):

>>> data = [45,78,120,47,58,50,32,34]
>>> print (list(process(data)))
[[45, 78, 120], [47, 58], [50], [32, 34]]

Joke apart, if you need to group items in a list itertools.groupby deserves a little bit of attention. Not always the easiest/best answer -- but worth to make a try...

---

EDIT: If you don't like closures -- and prefer using an object to hold the state, here is an alternative:

class process:
    def __call__(self, lst):
        if len(lst) < 1:
            return lst

        self.prev = lst[0]
        self.n = 0

        return [ list(g) for k, g in itertools.groupby(lst, self._grouper) ]

    def _grouper(self, x):
        if x < self.prev:
            self.n += 1

        self.prev = x
        return self.n



data = [45,78,120,47,58,50,32,34]
print (list(process()(data)))

---

EDIT2: Since I prefer closures ... but @torek don't like the dictionary syntax, here a third variation around the same solution:

import itertools

def process(lst):
    # Guard clause against empty lists
    if len(lst) < 1:
        return lst

    # use an object here to work around closure limitations
    state = type('State', (object,), dict(prev=lst[0], n=0))

    def grouper(x):
        if x < state.prev:
            state.n += 1

        state.prev = x
        return state.n

    return [ list(g) for k, g in itertools.groupby(lst, grouper) ]

data = [45,78,120,47,58,50,32,34]
print (list(process(data)))

Answer 3

@uselpa's version is fine. Here's mine (same issue with [50] instead of just 50) that uses collections.deque to be a little more efficient, and also some long comments...

#! /usr/bin/env python

from collections import deque

def process(lst):
    """
    Given a list of values that is not sorted (such that for some
    valid indices i,j, i<j, sometimes lst[i] > lst[j]), produce a
    new list-of-lists, such that in the new list, each sublist *is*
    sorted:
        for all sublist \elem returnval:
            assert_is_sorted(sublist)
    and furthermore this is the minimal set of sublists required
    to achieve the condition.

    Thus, if the input list lst is actually sorted, this returns
    [list(lst)].
    """
    def sublist(deq):
        """
        Pop items off the front of deque deq until the next one
        goes backwards.  Return the constructed sub-list.
        """
        sub = [deq.popleft()]
        while deq and deq[0] >= sub[-1]:
            sub.append(deq.popleft())
        return sub

    # Make a copy of lst before modifying it; use a deque so that
    # we can pull entries off it cheaply.
    deq = deque(lst)
    output = []
    ret = []
    while deq:
        ret.append(sublist(deq))
    return ret

print process([45,78,120,47,58,50,32,34])

(Incidentally, in the days before collections.deque I'd probably just use a reversed copy of lst and use lst.pop() in sublist. That's not quite as obvious, though.)