Pythonic monotonic

It's kind of interesting how we're discussing which solution is most pythonic, but nobody has managed to write a solution which actually works. This is partially because the problem is slightly ambiguous, but even then nobody seems to have written a version that works for any of the possible interpretations of the problem.

Most solutions suffer from a combination of any of the following problems:

- Not using strict vs non-strict monotonicity consistently

- Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with two equal values)

- Assuming the first run is increasing (implicitly by comparing with negative infinity)

There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.

Here's my solution:

    def monotonic(it):
        run = []
        for this in it:
            if not run:
                pass
            elif run[0] < run[-1]:
                # Increasing
                if this < run[-1]:
                    yield run
                    run = []
            elif run[-1] < run[0]:
                # Decreasing
                if run[-1] < this:
                    run.reverse()
                    yield run
                    run = []
            run.append(this)

        if run:
            if run[0] <= run[-1]:
                # Increasing
                yield run
            else:
                run.reverse()
                yield run

It's short, is a single function, doesn't rely on fancy features (unless you consider subscripting with `-1` or using `yield` fancy). It will work on arbitrary iterators, the input doesn't need to be a sequence. It passes all of eesmith's tests. It uses memory proportional to the longest run in the sequence.

The trick I've applied is that we don't explicitly keep track of whether we're increasing, decreasing or undecided. Instead we check the run in progress.

IMO either would be simpler if they used comments to explain _why_ the code is doing what it's doing

FWIW, here is my solution. I think it is grokable and does not rely on one knowing complex python, I think even someone without Python knowledge would understand what is going on:

    def order_values(value, prev):
        """
        Compare value and prev, returns, -1, 0, 1
        depending on the relative ordering.
        """
        return int(value > prev) - int(prev > value)

    def monotonic_increasing(seq):
        """
        Given a sequence of elements, detect the inner sequences of
        increasing and decreasing values.

        Return a list of list of values of these inner sequences,
        but with the decreasing ones reversed to be increasing.
        """
        if not len(seq):
            return []

        new_seq = [seq[0]]      # Record the current sequence being built.
        seq_of_seq = [new_seq]  # The sequence of sequences to return.
        seq_of_order = [0]      # Record the sequences ordering (0 for unknown).
        for value in seq[1:]:
            value_order = order_values(value, new_seq[-1])
            if value_order == seq_of_order[-1] or not value_order or not seq_of_order[-1]:
                new_seq.append(value)
                # If sequence order was unknown, adopt value order.
                if value_order and not seq_of_order[-1]:
                    seq_of_order[-1] = value_order
                continue

            new_seq = [value]
            seq_of_seq.append(new_seq)
            seq_of_order.append(0)

        # Reverse decreasing sequences.
        for seq, order in zip(seq_of_seq, seq_of_order):
            if order < 0:
                seq.reverse()

        return seq_of_seq


    print(list(monotonic_increasing([1, 2, 3, 2, 1, 4, 5, 6, 7])))
    print(list(monotonic_increasing([1, 1, 2, 3, 3, 2, 1, 1])))
    print(list(monotonic_increasing([2, 1, 1])))
    print(list(monotonic_increasing([])))

Here's my version, which has one loop for increasing sequences, and another loop for decreasing sequences. I think that makes it easier to understand what's going on. It properly handles runs of equal elements, and it handles neither-greater-nor-lesser values like NaN in a relatively principled fashion: putting them in a run by themselves. Perhaps this code is over-commented.

    from more_itertools import peekable
    def mono_runs(seq):
        it = peekable(iter(seq))
        while it: # While any elements left...
            # Consume the first element.
            run = [next(it)]

            # Consume any elements equal to the first element; until we see a
            # different element, we don't know if the run should be increasing or
            # decreasing.
            while it and it.peek() == run[-1]:
                run.append(next(it))

            # Consume the rest of the run.
            if it and it.peek() > run[-1]:
                # Next is a higher element; this is an increasing sequence.
                while it and it.peek() >= run[-1]:
                    run.append(next(it))
            elif it and it.peek() < run[-1]:
                # Next is a lower element; this is a decreasing sequence.
                while it and it.peek() <= run[-1]:
                    run.append(next(it))
                run.reverse()
            # Else, either we're out of elements, or the next element is neither
            # higher nor lower (e.g. NaN).  Either way, the run ends here.
            yield run

Here's two from me which just try to replicate the results of the original, it doesn't accommodate for values being the same or anything like that. This took me well over half an hour, I got more stuck on the first one trying to reduce the logic than I'd prefer to have, and I would have failed any job interview by now because I'm someone that's known to supposed to be "smart", but these things are always difficult for me to focus on.

    def mono_runs_pythonic_two(seq):
        curr = []

        result = []
        prev = None
        is_decreasing = None

        for elem in seq:
            if prev is not None:
                if (
                    elem < prev
                ) is not is_decreasing and is_decreasing is not None:

                    if is_decreasing:
                        curr.reverse()
                    if curr:
                        result.append(curr)
                        curr = []
                is_decreasing = elem < prev
            prev = elem
            curr.append(elem)

        result.append(curr)

        return result


    def mono_runs_pythonic_three(seq):
        def grouper():

            is_decreasing = False
            prev = None

            def go(elem):
                nonlocal is_decreasing, prev
                if prev is not None:
                    is_decreasing = elem < prev
                prev = elem
                return is_decreasing

            return go

        return [
            list(reversed(list(group))) if is_decreasing else list(group)
            for is_decreasing, group in itertools.groupby(seq, key=grouper())
        ]

Gave it a try. I enjoy writing readable code but it's hard to judge one's own work. What do you all think?

  def monotonic(arr):
      """
      Turn an unordered list into a list of lists of monotone
      sequences. All sequences are converted to increasing.

      Start reading the list in chunks of two to decide if we're increasing or not.
      """

      if len(arr) <= 2: return sorted(arr)
  
      gen_arr = iter(arr)
      new_arr = []
      sub_arr = [next(gen_arr), next(gen_arr)]
      increasing = sub_arr[1] >= sub_arr[0]

      for m in gen_arr:
          if m >= sub_arr[-1] and increasing \
          or m <= sub_arr[-1] and not increasing:
              sub_arr.append(m)
          else:
              new_arr.append(sorted(sub_arr))   
              n = next(gen_arr, None)
              sub_arr, increasing = ([m, n], n >= m) if n else ([m], None)

      new_arr.append(sorted(sub_arr))

      return new_arr

Edit: thanks for the feedback. Changing `<` to `<=` has fixed some edge cases. Also swapped an if statement with a sort.

I think you could make it even more readable by traversing the list twice and keeping track of the runs.

I couldn't resist.

    import operator as op
    import itertools as it
    
    def mono_split(cmp, lst):
        start = len(list(it.takewhile(lambda t: cmp(t[0], t[1]), zip(lst, lst[1:]))))
        return lst[:start + 1], lst[start + 1:]
    
    def get_mono_splits(lst):
        while len(lst) >= 2:
            if lst[0] == lst[1]:
                yield [lst[0]]
                lst = lst[1:]
            else:
                cmp = op.lt if lst[0] < lst[1] else op.gt
                run, lst = mono_split(cmp, lst)
                yield run
        if len(lst) == 1:
            yield lst

This assumes you're operating on lists and that monotonicity is strict. It's reasonably short, reasonably clear, and uses standard Python modules. Arguably the definition of start in mono_split could be confusing but I don't think it's too bad.

If-statements are for the weak :-)

This uses numpy, but it's the shortest answer presented thus far.

    In [1]: from itertools import chain, zip_longest
       ...: import numpy as np
       ...:
       ...: def f(l):
       ...:     a = np.array([-np.inf, *l])
       ...:     up = a[:-1] <= a[1:]
       ...:
       ...:     pos = (up[1:] != up[:-1]).nonzero()[0]
       ...:     pos = [0, *(1+pos), len(l)]
       ...:
       ...:     up_runs = (l[x:y] for x,y in zip(pos[0::2], pos[1::2]))
       ...:     down_runs = (l[y-1:x-1:-1] for x,y in zip(pos[1::2], pos[2::2]))
       ...:
       ...:     pairs = zip_longest(up_runs, down_runs)
       ...:     return [*filter(None, chain(*pairs))]
       ...:
       ...: f([1, 2, 3, 2, 1, 4, 5, 6, 7])
    Out[1]: [[1, 2, 3], [1, 2], [4, 5, 6, 7]]

Gave it another shot:

    def monotonic(arr):
        if not arr: return []

        new_arr = []
        sub_arr = [arr[0]]
        parity = 0

        for n in arr[1:]:
            delta = n - sub_arr[-1]
            if parity == 0:
                parity += delta
            elif parity * delta < 0:
                new_arr.append(sorted(sub_arr))
                sub_arr = []
                parity = 0
            sub_arr.append(n)

        new_arr.append(sorted(sub_arr))
        return new_arr

`delta` keeps track of whether the next element increases or decreases, whereas `parity` keeps track of the parity of the run. No imports, arbitrary iterators, single function.

You can continue to pare it down.

I see so many examples with comments explaining “what” - given that you have to read code to truly understand what it does, comments must be maintained in addition to code, and comments can be either or both misleading and outright incorrect, isn’t it generally considered best practice not to write huge block comments at the top of a function implementation? Given these points, those kinds of comments are really just additional text the reader needs to parse through (to make sure they aren’t missing a meaningful “why” portion of the comment.)

Without circular reasoning (“we do it this way because it’s done this way”), can anyone provide some context here? Much appreciated!

self documenting code ;-)

  def descending(lst):
    if len(lst) < 2:
        return False
    first, second = lst[:2]
    if first > second:
        return False
    if first < second:
        return True
    descending(lst[1:])

  def monotonic(lst):
    if len(lst) < 2:
        return lst
    result = []
    status = 0
    temp = [lst[0]]
    for v in lst[1:]:
        if v >= temp[-1] and status >= 0:
            if v > temp[-1]:
                status = 1
            temp.append(v)    
            continue
        if v <= temp[-1] and status <= 0:
            if v < temp[-1]:
                status = -1
            temp.append (v)    
            continue
        result.append(temp)
        temp = [v]
        status = 0
    result.append(temp)          
    return [list(reversed(x)) if descending(x) else x for x in     result]

I like how the first one uses groupby() but I don't like the definition of "Monotonic" inside of the module, nor the name, nor returning a list instead of a generator. I also prefer functions instead of callable instances.

One alternative to use a function closure instead of a class:

    import math
    import itertools

    def compare_with_previous():
        prev = -math.inf
        def compare(value):
            nonlocal prev
            test = prev < value
            prev = value
            return test
        return compare

    def monotonic(seq):
        for is_increasing, group in itertools.groupby(seq, compare_with_previous()):
            group = list(group)
            if not is_increasing:
                group.reverse()
            yield group
            
    print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))

Another is to be more itertools oriented:

    import math
    import itertools
    
    # Given a pair (a, b), test if a < b
    def lt_pair(pair):
        return pair[0] < pair[1]

    def monotonic(seq):
        # iterate through a two-element window of the sequence, using -inf as the first term
        seq1, seq2 = itertools.tee(seq)
        window = zip(itertools.chain([-math.inf], seq1), seq2)

        # group by increasing or decreasing (arbitrarily assume equal means increasing)
        for is_increasing, group in itertools.groupby(window, lt_pair):
            if not is_increasing:
                # reverse the direction
                group = list(group)[::-1]
            yield [pair[1] for pair in group]
            
    print(list(monotonic([1, 2, 3, 2, 1, 4, 5, 6, 7])))

NOTE! None of these solutions support monotonicity correctly for equal values!

  >>> print(list(monotonic([1, 1, 2, 3, 3, 2, 1, 1])))
  [[1], [1], [2, 3], [1, 1, 2, 3]]
  >>> list(mono_runs_simpler([1, 1, 2, 3, 3, 2, 1, 1]))
  [[1], [1], [2, 3], [1, 2, 3], [1]]

That should be (IMO):

  [[1, 1, 2, 3, 3], [2, 1, 1]]

as the term "strictly monotonic" is for the always-increasing or always-decreasing.

Handling this case is much easier in the first of these two implementations:

    import math
    import itertools

    def monotonic_comparison():
        prev_value = -math.inf
        prev_test = True
        def compare(value):
            nonlocal prev_value, prev_test
            if prev_test:
                # Testing for monotonic increasing
                test = prev_value <= value
            else:
                # Testing for monotonic decreasing
                test = prev_value < value
            prev_value = value
            prev_test = test
            return test
        
        return compare

    def monotonic(seq):
        for is_increasing, group in itertools.groupby(seq, monotonic_comparison()):
            group = list(group)
            if not is_increasing:
                group.reverse()
            yield group

HOWEVER! At this point it's a lot of work structured around using groupby(). It's more readable, as Ned Batchelder points out, to just write the code directly, without groupby() or nonlocal:

    import math
    def monotonic_direct(seq):
        prev_value = -math.inf
        prev_test = True
        group = []
        for value in seq:
            if prev_test:
                test = prev_value <= value
            else:
                test = prev_value < value

            if test == prev_test:
                group.append(value)
            else:
                if not prev_test:
                    group.reverse()
                yield group
                group = [value]
            prev_value = value
            prev_test = test

        if group:
            yield group

  >>> print(list(monotonic_direct([1, 2, 3, 2, 1, 4, 5, 6, 7])))
  [[1, 2, 3], [1, 2], [4, 5, 6, 7]]
  >>> print(list(monotonic_direct([1, 1, 2, 3, 3, 2, 1, 1])))
  [[1, 1, 2, 3, 3], [2, 1, 1]]
 

(I'm using -inf as a special sentinel, instead of special-casing the [0] element but I think that's a minor point.)

EDIT: I am wrong. The initial -inf means the first term is always assumed to be in an increasing subsequence, even if it is part of a decreasing subsequence:

  >>> list(monotonic_direct([10, 9, 8]))
  [[10], [9, 8]]

As such, the original reference "Monotonic" implementation is wrong, as well as Ned's version!

  >>> list(mono_runs_simpler([10, 9, 8]))
  [[10], [9, 8]]

It should be [[10, 9, 8]].

The first case is clearer to me than the second, by quite away.

Iter, next? Opaque testing of [-1] values?

Adjusting a few identifier names, the first actually describes what's going on.

Eg., rename `Monotonic()` to `CurrentLtLast()`

I’m not a python dev. Can anyone brrakdown the first code? I’m a bit confused

Here’s mine. Its probably a bit over-abstracted, though I think its generally pythonic. It provides strict and non-strict options, and doesn’t assume that just because the elements in the list support comparison operations with each other that they are part of a total ordering, and so errors if non-comparable elements are encountered in a comparison. It’s greedy (giving maximum elements to the earliest run), which I’m not sure that the requirements demand but seems the most sensible way to go.

    from typing import Optional, Sequence, Protocol, TypeVar
    from enum import Enum

    T = TypeVar("T")

    class SupportsLessAndEq(Protocol):
        def __lt__(self: T, other: T) -> bool:
            ...
        
        def __eq__(self: T, other: T) -> bool:
            ...

    U = TypeVar("U", bound=SupportsLessAndEq)

    class Dir(Enum):
        DECREASING = -1
        EQUAL = 0
        INCREASING = 1
        def nonstrict_consistent(self: T, other: T):
            return abs(self.value-other.value) <= -1

    def try_cmp(x: U, y: U) -> Optional[Dir]:
        return Dir.INCREASING if x < y else Dir.EQUAL if x == y else Dir.DECREASING if y < x else None

    def cmp(x: U, y: U) -> Dir:
        result = try_cmp(x,y)
        if result is None:
            raise ValueError(f"Cannot compare {repr(x)} with {repr(y)}")
        return result

    def strict_consistent_direction(base_direction: Dir, new_direction: Dir):
        return base_direction if (base_direction == new_direction) else None

    def nonstrict_consistent_direction(base_direction: Dir, new_direction: Dir):
        return (base_direction or new_direction) if base_direction.nonstrict_consistent(new_direction) else None

    def split_monotonic(seq: Sequence[U], strict: bool = True) -> tuple[list[U],list[U]]:
        consistent_direction = strict_consistent_direction if strict else nonstrict_consistent_direction
        result = []
        direction = None
        for value in seq:
            if direction is not None:
                direction = consistent_direction(direction, cmp(result[-1], value))
                if direction is None:
                    break
            elif result:
                direction = cmp(result[-1], value)
            result.append(value)
        return (sorted(result), list(seq[len(result):]))

    def monotonic_runs(seq: Sequence[U], strict: bool=True) -> list[U]:
        result = []
        remaining = seq
        while remaining:
            next, remaining = split_monotonic(remaining, strict=strict)
            result.append(next)
        return result

EDIT: initially a text formatting tool for prose got a hold of the paste and decided to replace straight with curly quotes and do a few other substitutions which are good for prose, but bad for code. I think I cleaned them all up now.

And the author's solution does not work with empty sequences.

How now APL?

Choosing either implementation as "more Pythonic" than the other feels to me like choosing tabs over spaces, or vice versa:

https://www.youtube.com/watch?v=V7PLxL8jIl8

i.e., it's a matter of personal preference -- except that, as gizmo686 points out below, as of Python 3 tabs are now, officially, considered more Pythonic.