Check list monotonicity

Question

How do I efficiently check list monotonicity? i.e. that it is either a non-decreasing or non-increasing set of ordered values?

Examples:

[0, 1, 2, 3, 3, 4]   # This is a monotonically increasing list
[4.3, 4.2, 4.2, -2]  # This is a monotonically decreasing list
[2, 3, 1]            # This is neither

Tsan

It's better to use the terms "strictly increasing" or "non decreasing" to leave any ambiguity out (and in a similar way it's better to avoid "positive" and use instead either "non negative" or "strictly positive") – Boigie

if you are looking for extracting the data part with certain monotonicity, please have a look at: github.com/Weilory/python-regression/blob/master/regression/… – Ebneter

Answer 1

Are repeated values (e.g. [1, 1, 2]) monotonic?

If yes:

def non_decreasing(L):
    return all(x<=y for x, y in zip(L, L[1:]))

def non_increasing(L):
    return all(x>=y for x, y in zip(L, L[1:]))

def monotonic(L):
    return non_decreasing(L) or non_increasing(L)

If no:

def strictly_increasing(L):
    return all(x<y for x, y in zip(L, L[1:]))

def strictly_decreasing(L):
    return all(x>y for x, y in zip(L, L[1:]))

def strictly_monotonic(L):
    return strictly_increasing(L) or strictly_decreasing(L)

Boigie

This is clear, idiomatic Python code, and its complexity is O(n) where the sorting answers are all O(n log n). An ideal answer would iterate over the list only once so it works on any iterator, but this is usually good enough and it's by far the best answer among the ones so far. (I'd offer a single-pass solution, but the OP prematurely accepting an answer curbs any urge I might have to do so...) – Dahlberg

just out of curiosity tested your implementation against using sorted. Yours is clearly a lot slower [ I used L = range(10000000) ]. It seems complexity of all is O(n), and I could not find implementation of zip. – Team

Sort is specialized if the list is already sorted. Did you try the speed with a randomly shuffled list? Also note that with sort you cannot distinguish between strictly increasing and non decreasing. Also consider that with Python 2.x using itertools.izip instead of zip you can get an early exit (in python 3 zip already works like an iterator) – Boigie

@Glenn - I have changed answer acceptance in the past, don't be discouraged :) – Tsan

@HughBothwell: I just posted a simple alternative solution without the potentially expensive temporary slices. – Tussis

@GlennMaynard there's now a single-pass solution that works on any iterator here – Protractile

Answer 2

If you have large lists of numbers it might be best to use numpy, and if you are:

import numpy as np

def monotonic(x):
    dx = np.diff(x)
    return np.all(dx <= 0) or np.all(dx >= 0)

should do the trick.

Laguna

Note that dx[0] is np.nan. You might want to use: dx = np.diff(x)[1:] to skip past it. Otherwise, at least for me, the np.all() calls always return False. – Gudrun

@Ryan, why would dx[0] be NaN? What is your input array? – Eudemonics

N/m, I was thinking that np.diff() made the first element NaN so the shape of the output matched the input, but that was actually a different piece of code that did that that bit me. :) – Gudrun

Answer 3

import itertools
import operator

def monotone_increasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.le, pairs))

def monotone_decreasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.ge, pairs))

def monotone(lst):
    return monotone_increasing(lst) or monotone_decreasing(lst)

This approach is O(N) in the length of the list.

Senile

The Correct(TM) solution IMO. Functional paradigm for the win! – Unchaste

why using itertools instead of plain generators? – Boigie

Functional paradigms are usually not "the win" in Python. – Dahlberg

@Boigie Habit, mostly. On the other hand, map is exactly the abstraction needed, here, so why recreate it with a generator expression? – Senile

Calculating pairs is O(N) as well. You could make pairs = itertools.izip(lst, itertools.islice(lst, 1, None)). – Enciso

@Michael: I think you've got it the other way around. Generators are a better (cleaner) alternative to map in many cases... see python.org/dev/peps/pep-0289 – Boigie

Of course, monotone is more expensive than strictly needed since there is no need to traverse the list twice. This is verging on pedantry though, my specialist subject! – Quitclaim

@Boigie Many cases, but not all. I'd say this is a case of De gustibus non est disputandum. – Senile

On Python 3.10+ all(itertools.starmap(operator.le, itertools.pairwise(lst))) is even faster, especially when the list gets close to taking up your computer's entire memory (about 3 times faster). The only drawback is now if you pass a generator to the function it silently produces a wrong answer instead of throwing an error. – Protractile

Answer 4

The top answer only works with sequences (lists), here's a more general solution that works with any iterable (lists and generators) for Python 3.10+:

from itertools import pairwise

def monotonic(iterable, strict=False):
    up = False
    down = False
    for first, second in pairwise(iterable):
        if first < second:
            if down:
                return False
            up = True
        elif first > second:
            if up:
                return False
            down = True
        elif strict:
            # first and second are equal.
            return False
    return True

Pass strict=True you want to return False for repeated elements, e.g. [1, 1]:

Note that itertools.pairwise is only available on Python 3.10+, on Python 3.9 and older you'll need to re-implement it:

from itertools import tee

def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)

Genous

Answer 5

The pandas package makes this convenient.

import pandas as pd

The following commands work with a list of integers or floats.

Monotonically increasing (≥):

pd.Series(mylist).is_monotonic_increasing

Strictly monotonically increasing (>):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_increasing

Alternative using an undocumented private method:

pd.Index(mylist)._is_strictly_monotonic_increasing

Monotonically decreasing (≤):

pd.Series(mylist).is_monotonic_decreasing

Strictly monotonically decreasing (<):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_decreasing

Alternative using an undocumented private method:

pd.Index(mylist)._is_strictly_monotonic_decreasing

Nabataean

The pandas method is now .is_monotonic which I think makes sense because it can be used in conjunction with the Python not keyword intuitively. This follows other conventions in Python such as heapq min and max heaps, where only min heap is default but max heap is just a reverse implementation with multiplying by -1. – Azpurua

Answer 6

I benchmarked these non-numpy/pandas answers:

1. @6502's accepted/top answer
2. @Michael J. Barber's itertools.starmap answer
3. @Jochen Ritzel's itertools.pairwise answer
4. @akira's operator answer
5. @chqrlie's range(len()) answer
6. @Asterisk's and @Senthil Kumaran's naive sorted() answer and answer

on Python 3.11 on an M1 Macbook Air with 8GB of RAM with perfplot on trivially monotonic input [0, 1, 2, ... n] (lower is better):

almost monotonic input, except for the last element [0, 1, 2, ... n, 0]:

and a randomly shuffled list:

and found that

• Sorting is 4 times faster than the next best method if the list is monotonic but 10 (or more) times slower when it's not or if the number of elements out of order is greater than ~1. The more out of order the list, corresponds to a slower result.
• The two answers that do early stoping are much faster for random lists, because you're very likely to see from the first few elements that it's not monotonic

Here's the code:

import itertools
from itertools import pairwise
import operator

import random
import perfplot
import matplotlib
matplotlib.rc('font', family="monospace")

fns = []

def non_decreasing(L):
    return all(x<=y for x, y in zip(L, L[1:]))
def non_increasing(L):
    return all(x>=y for x, y in zip(L, L[1:]))
def zip_monotonic(L):
    return non_decreasing(L) or non_increasing(L)
fns.append([zip_monotonic, '1. zip(l, l[1:])'])

def monotone_increasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.le, pairs))
def monotone_decreasing(lst):
    pairs = zip(lst, lst[1:])
    return all(itertools.starmap(operator.ge, pairs))
def starmap_monotone(lst):
    return monotone_increasing(lst) or monotone_decreasing(lst)
fns.append([starmap_monotone, '2. starmap(zip(l, l[1:]))'])

# def _monotone_increasing(lst):
#     return all(itertools.starmap(operator.le, itertools.pairwise(lst)))
# def _monotone_decreasing(lst):
#     return all(itertools.starmap(operator.ge, itertools.pairwise(lst)))
# def starmap_pairwise_monotone(lst):
#     return _monotone_increasing(lst) or _monotone_decreasing(lst)
# fns.append([starmap_pairwise_monotone, 'starmap(pairwise)'])

def pairwise_monotonic(iterable):
    up = True
    down = True
    for prev, current in pairwise(iterable):
        if prev < current:
            if not up:
                return False
            down = False
        elif prev > current:
            if not down:
                return False
            up = False
    return True
fns.append([pairwise_monotonic, '3. pairwise()'])

def operator_first_last_monotonic(lst):
    op = operator.le
    if lst and not op(lst[0], lst[-1]):
        op = operator.ge
    return all(op(x, y) for x, y in zip(lst, lst[1:]))
fns.append([operator_first_last_monotonic, '4. operator(zip(l, l[1:]))'])

def __non_increasing(L):
    return all(L[i] >= L[i+1] for i in range(len(L)-1))
def __non_decreasing(L):
    return all(L[i] <= L[i+1] for i in range(len(L)-1))
def range_monotonic(L):
    return __non_increasing(L) or __non_decreasing(L)
fns.append([pairwise_monotonic, '5. range(len(l))'])

# def monotonic_iter_once(iterable):
#     up, down = True, True
#     for i in range(1, len(iterable)):
#         if iterable[i] < iterable[i-1]: up = False
#         if iterable[i] > iterable[i-1]: down = False
#     return up or down
# fns.append([monotonic_iter_once, 'range(len(l)) once'])

def sorted_monotonic(seq):
    return seq == sorted(seq) or seq == sorted(seq, reverse=True)
fns.append([sorted_monotonic, '6. l == sorted(l)'])


def random_list(n):
    l = list(range(n))
    random.Random(4).shuffle(l)
    return l


setups = [
    (29, lambda n: list(range(n)), 'monotonic.png'),
    (29, lambda n: list(range(n)) + [0], 'non-monotonic.png'),
    (26, random_list, 'random.png'),
]
kernels, labels = zip(*fns)

for (size, setup, filename) in setups:
    out = perfplot.bench(
        setup=setup,
        kernels=kernels,
        labels=labels,
        n_range=[2**k for k in range(size)],
        xlabel="n",
    )
    out.show(
        logx=True,  # set to True or False to force scaling
        logy=True,
        # relative_to=5,  # plot the timings relative to one of the measurements
    )
    out.save(filename, transparent=True, bbox_inches="tight")

Lozar

I did not try @Assem Chelli's method as it required knowledge of the max item in the list – Lozar

Could you include mine? Preferably using Python 3.12 or at least 3.11 (so it's not a step back, and because CPython has had nice speed improvements in 3.11 and later). – Perspicacious

@StefanPochmann I don't have matplotlib on my current laptop. Feel free to run my code (provided at the bottom of my answer) and edit this answer with your results. – Lozar

Answer 7

Here is a solution similar to @6502's answer with simpler iterators and no potentially expensive temporary slices:

def non_decreasing(L):
    return all(L[i] <= L[i+1] for i in range(len(L)-1))

def non_increasing(L):
    return all(L[i] >= L[i+1] for i in range(len(L)-1))

def monotonic(L):
    return non_decreasing(L) or non_increasing(L)

def strictly_increasing(L):
    return all(L[i] < L[i+1] for i in range(len(L)-1))

def strictly_decreasing(L):
    return all(L[i] > L[i+1] for i in range(len(L)-1))

def strictly_monotonic(L):
    return strictly_increasing(L) or strictly_decreasing(L)

Tussis

On Python 3.11 this is 10-20% slower for a list like list(range(2**n)) + [1] than 6502's code once the list is over 200-300 elements, up until then they're equal, for lists with 100's of millions or a billion elements this method is like 3 times faster (my laptop has 8GB of RAM). itertools.pairwise is generally slightly better than either. – Protractile

Answer 8

import operator

def is_monotonic(lst):
    op = operator.le
    if lst and not op(lst[0], lst[-1]):
        op = operator.ge
    return all(op(x, y) for x, y in zip(lst, lst[1:]))

Lightfingered

Answer 9

Here is a functional solution using reduce of complexity O(n):

is_increasing = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999

is_decreasing = lambda L: reduce(lambda a,b: b if a > b else -9999 , L)!=-9999

Replace 9999 with the top limit of your values, and -9999 with the bottom limit. For example, if you are testing a list of digits, you can use 10 and -1.

---

I tested its performance against @6502's answer and its faster.

Case True: [1,2,3,4,5,6,7,8,9]

# my solution .. 
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([1,2,3,4,5,6,7,8,9])"
1000000 loops, best of 3: 1.9 usec per loop

# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([1,2,3,4,5,6,7,8,9])"
100000 loops, best of 3: 2.77 usec per loop

Case False from the 2nd element: [4,2,3,4,5,6,7,8,7]:

# my solution .. 
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([4,2,3,4,5,6,7,8,7])"
1000000 loops, best of 3: 1.87 usec per loop

# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([4,2,3,4,5,6,7,8,7])"
100000 loops, best of 3: 2.15 usec per loop

Limulus

This is not a good way to do it. – Protractile

Answer 10

Here's a variant that accepts both materialized and non-materialized sequences. It automatically determines whether or not it's monotonic, and if so, its direction (i.e. increasing or decreasing) and strictness. Inline comments are provided to help the reader. Similarly for test-cases provided at the end.

    def isMonotonic(seq):
    """
    seq.............: - A Python sequence, materialized or not.
    Returns.........:
       (True,0,True):   - Mono Const, Strict: Seq empty or 1-item.
       (True,0,False):  - Mono Const, Not-Strict: All 2+ Seq items same.
       (True,+1,True):  - Mono Incr, Strict.
       (True,+1,False): - Mono Incr, Not-Strict.
       (True,-1,True):  - Mono Decr, Strict.
       (True,-1,False): - Mono Decr, Not-Strict.
       (False,None,None) - Not Monotonic.
    """    
    items = iter(seq) # Ensure iterator (i.e. that next(...) works).
    prev_value = next(items, None) # Fetch 1st item, or None if empty.
    if prev_value == None: return (True,0,True) # seq was empty.

    # ============================================================
    # The next for/loop scans until it finds first value-change.
    # ============================================================
    # Ex: [3,3,3,78,...] --or- [-5,-5,-5,-102,...]
    # ============================================================
    # -- If that 'change-value' represents an Increase or Decrease,
    #    then we know to look for Monotonically Increasing or
    #    Decreasing, respectively.
    # -- If no value-change is found end-to-end (e.g. [3,3,3,...3]),
    #    then it's Monotonically Constant, Non-Strict.
    # -- Finally, if the sequence was exhausted above, which means
    #    it had exactly one-element, then it Monotonically Constant,
    #    Strict.
    # ============================================================
    isSequenceExhausted = True
    curr_value = prev_value
    for item in items:
        isSequenceExhausted = False # Tiny inefficiency.
        if item == prev_value: continue
        curr_value = item
        break
    else:
        return (True,0,True) if isSequenceExhausted else (True,0,False)
    # ============================================================

    # ============================================================
    # If we tricked down to here, then none of the above
    # checked-cases applied (i.e. didn't short-circuit and
    # 'return'); so we continue with the final step of
    # iterating through the remaining sequence items to
    # determine Monotonicity, direction and strictness.
    # ============================================================
    strict = True
    if curr_value > prev_value: # Scan for Increasing Monotonicity.
        for item in items:
            if item < curr_value: return (False,None,None)
            if item == curr_value: strict = False # Tiny inefficiency.
            curr_value = item
        return (True,+1,strict)
    else:                       # Scan for Decreasing Monotonicity.
        for item in items: 
            if item > curr_value: return (False,None,None)
            if item == curr_value: strict = False # Tiny inefficiency.
            curr_value = item
        return (True,-1,strict)
    # ============================================================


# Test cases ...
assert isMonotonic([1,2,3,4])     == (True,+1,True)
assert isMonotonic([4,3,2,1])     == (True,-1,True)
assert isMonotonic([-1,-2,-3,-4]) == (True,-1,True)
assert isMonotonic([])            == (True,0,True)
assert isMonotonic([20])          == (True,0,True)
assert isMonotonic([-20])         == (True,0,True)
assert isMonotonic([1,1])         == (True,0,False)
assert isMonotonic([1,-1])        == (True,-1,True)
assert isMonotonic([1,-1,-1])     == (True,-1,False)
assert isMonotonic([1,3,3])       == (True,+1,False)
assert isMonotonic([1,2,1])       == (False,None,None)
assert isMonotonic([0,0,0,0])     == (True,0,False)

I suppose this could be more Pythonic, but it's tricky because it avoids creating intermediate collections (e.g. list, genexps, etc); as well as employs a fall/trickle-through and short-circuit approach to filter through the various cases: E.g. Edge-sequences (like empty or one-item sequences; or sequences with all identical items); Identifying increasing or decreasing monotonicity, strictness, and so on. I hope it helps.

Kepler

Answer 11

Here are implementations that are both general (any input iterables are supported, including iterators, not just sequences) and efficient (the space required is constant, no slicing that performs a temporary shallow copy of the input):

import itertools

def is_increasing(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    next(y_it, None)
    if strict:
        return all(x < y for x, y in zip(x_it, y_it))
    return all(x <= y for x, y in zip(x_it, y_it))

def is_decreasing(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    next(y_it, None)
    if strict:
        return all(x > y for x, y in zip(x_it, y_it))
    return all(x >= y for x, y in zip(x_it, y_it))

def is_monotonic(iterable, strict=False):
    x_it, y_it = itertools.tee(iterable)
    return is_increasing(x_it, strict) or is_decreasing(y_it, strict)

A few test cases:

assert is_monotonic([]) is True
assert is_monotonic(iter([])) is True
assert is_monotonic([1, 2, 3]) is True
assert is_monotonic(iter([1, 2, 3])) is True
assert is_monotonic([3, 2, 1]) is True
assert is_monotonic(iter([3, 2, 1])) is True
assert is_monotonic([1, 3, 2]) is False
assert is_monotonic(iter([1, 3, 2])) is False
assert is_monotonic([1, 1, 1]) is True
assert is_monotonic(iter([1, 1, 1])) is True

assert is_monotonic([], strict=True) is True
assert is_monotonic(iter([]), strict=True) is True
assert is_monotonic([1, 2, 3], strict=True) is True
assert is_monotonic(iter([1, 2, 3]), strict=True) is True
assert is_monotonic([3, 2, 1], strict=True) is True
assert is_monotonic(iter([3, 2, 1]), strict=True) is True
assert is_monotonic([1, 3, 2], strict=True) is False
assert is_monotonic(iter([1, 3, 2]), strict=True) is False
assert is_monotonic([1, 1, 1], strict=True) is False
assert is_monotonic(iter([1, 1, 1]), strict=True) is False

Liquate

This raises a StopIteration error instead of returning True if you pass an empty iterable – Protractile

is_strictly_monotonic([]) to reproduce (I reposted my comment with the correct error) – Protractile

Also, your answer is a duplicate of Jochen Ritzel's – Protractile

@BorisVerkhovskiy You’re right, like John Ritzel’s implementation, my implementation has a flaw: it raises StopIteration for empty iterable inputs because of the next(iterator) call (instead of next(iterator, None)). But contrary to John Ritzel’s implementation, my implementation has another flaw: it traverses non-overlapping pairs and misses the first pair for iterator inputs because of the zip(iterable, iterator) call (instead of John Ritzel’s for loop or itertools.pairwise() equivalent code based on zip() and itertools.tee() that creates two independent iterators). – Misbeliever

@BorisVerkhovskiy There is a flaw in your monotonic() and strictly_monotic() implementations in your edits to John Ritzel’s answer: monotonic([1, 3, 2]) returns False (as expected) but monotonic(iter([1, 3, 2])) returns True (likewise for strictly_monotic). This is because non_decreasing(iterable) exhausts the iterator so non_increasing(iterable) gets en empty iterator as input so always returns True. To fix this you should pass two independent iterators as input to non_decreasing() and non_increasing() using itertools.tee(). – Misbeliever

Thanks for letting me know, nice catch. I just tried and his original code actually has the same bug. – Protractile

@BorisVerkhovskiy Welcome. Yes his original code has the same bug. Thanks for taking the time to improve the posts in this thread, I learnt a lot. – Misbeliever

@BorisVerkhovskiy Based on those lessons, I have added a few test cases to my answer. – Misbeliever

Answer 12

L = [1,2,3]
L == sorted(L)

L == sorted(L, reverse=True)

Team

I'd have gone for sorted() if it didn't actually sort anything, just check. Badly named -- sounds like a predicate when it isn't. – Unchaste

What's next? Using sorted(L)[0] instead of min? – Boigie

This is algorithmically poor; this solution is O(n log n), when this problem can be done trivially in O(n). – Dahlberg

@all agree with all of you, thanks for constructive criticism. – Team

I tested all the solutions in this thread here, and found that the sorted method actually is the best... if the list is actually monotonically increasing. If the list has any items out of order, it becomes the slowest. – Lozar

While this code may answer the question, providing additional context regarding how and/or why it solves the problem would improve the answer's long-term value. - From Review – Dripps

Answer 13

>>> seq = [0, 1, 2, 3, 3, 4]
>>> seq == sorted(seq) or seq == sorted(seq, reverse=True)

Ayotte

This is very very inefficient. – Rapscallion

@Rapscallion Why is it so inefficient? – Casebound

Because it can be done by reading the list once and keeping one extra variable. While the sort operation is slower. – Rapscallion

Answer 14

def IsMonotonic(data):
    ''' Returns true if data is monotonic.'''
    data = np.array(data)
    # Greater-Equal
    if (data[-1] > data[0]):
        return np.all(data[1:] >= data[:-1])
    # Less-Equal
    else:
        return np.all(data[1:] <= data[:-1])

My proposition (with numpy) as a summary of few ideas here. Uses

• casting to np.array for creation of bool values for each lists comparision,
• np.all for checking if all results are True
• checking diffrence between first and last element for choosing comparison operator,
• using direct comparison >=, <= instead of calculatin np.diff,

Euphonium

Answer 15

We can only iterate over the list once when checking if its either decreasing or increasing:

def is_monotonic(iterable):
    up = down = True
    for i in range(1, len(iterable)):
        if iterable[i] < iterable[i-1]: up = False
        if iterable[i] > iterable[i-1]: down = False
    return up or down

Transnational

This doesn't do early stoping. If we can tell from the first 3 elements that the answer is False it will still iterate over the entire list – Protractile

Answer 16

Solution 1: Barebones looping

Very efficient in my own testing (I'll try to get Matthew's plots updated), and also works for other iterables:

def monotonic(iterable):
    it = iter(iterable)
    for first in it:
        for x in it:
            if first != x:
                if first < x:
                    for y in it:
                        if x > y:
                            return False
                        x = y
                else:
                    for y in it:
                        if x < y:
                            return False
                        x = y
    return True

It finds a value that differs from the first value, and then depending on whether it's larger or smaller, enters a simple loop checking non-decreasing of the rest or a simple loop checking non-increasing of the rest.

Solution 2: sorted overlapping chunks

This combines the speed of sorted with short-circuiting. It reads and checks chunks of 1000 elements, overlapping so that the last element of one chunk is also included as the first element of the next chunk.

def monotonic(a):
    reverse = a[-1:] < a[:1]
    for i in range(0, len(a), 999):
        b = a[i : i+1000]
        if b != sorted(b, reverse=reverse):
            return False
    return True

Perspicacious