Python - How to check if a list is monotonic

Question

What is an effective and python way to check the monotony of a list?
that is, that it has monotonically increasing or decreasing 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 

Answer 1

 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 non_increasing(L): return all(x>=y for x, y in zip(L, L[1:])) def non_decreasing(L): return all(x<=y for x, y in zip(L, L[1:])) def monotonic(L): return non_increasing(L) or non_decreasing(L) 

Answer 2

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

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

gotta do the trick.

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 list length.

Answer 4

@ 6502 has the perfect code for lists, I just want to add a generic version that works for all sequences:

 def pairwise(seq): items = iter(seq) last = next(items) for item in items: yield last, item last = item def strictly_increasing(L): return all(x<y for x, y in pairwise(L)) def strictly_decreasing(L): return all(x>y for x, y in pairwise(L)) def non_increasing(L): return all(x>=y for x, y in pairwise(L)) def non_decreasing(L): return all(x<=y for x, y in pairwise(L)) 

Answer 5

 import operator, itertools def is_monotone(lst): op = operator.le # pick 'op' based upon trend between if not op(lst[0], lst[-1]): # first and last element in the 'lst' op = operator.ge return all(op(x,y) for x, y in itertools.izip(lst, lst[1:])) 

Answer 6

Here is a functional solution using reduce 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 upper limit of your values ​​and -9999 with the lower limit. For example, if you are testing a list of numbers, you can use 10 and -1 .

---

I tested my performance against @ 6502 answer and faster.

True Case: [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 

False case from the second 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 

Answer 7

I dated all the answers in this question under different conditions and found that:

• Sorting was the fastest with a long shot if the list was already monotonously growing.
• Sorting was the slowest with a long shot if the list was shuffled / random, or if the number of elements is out of order greater than 1. Moreover, the list, of course, corresponds to a slower result.
• Michael J. Barber's method was the fastest if the list was mostly monotonically increasing or completely random.

Here is the code to try:

 import timeit setup = ''' import random from itertools import izip, starmap, islice import operator def is_increasing_normal(lst): for i in range(0, len(lst) - 1): if lst[i] >= lst[i + 1]: return False return True def is_increasing_zip(lst): return all(x < y for x, y in izip(lst, islice(lst, 1, None))) def is_increasing_sorted(lst): return lst == sorted(lst) def is_increasing_starmap(lst): pairs = izip(lst, islice(lst, 1, None)) return all(starmap(operator.le, pairs)) if {list_method} in (1, 2): lst = list(range({n})) if {list_method} == 2: for _ in range(int({n} * 0.0001)): lst.insert(random.randrange(0, len(lst)), -random.randrange(1,100)) if {list_method} == 3: lst = [int(1000*random.random()) for i in xrange({n})] ''' n = 100000 iterations = 10000 list_method = 1 timeit.timeit('is_increasing_normal(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations) timeit.timeit('is_increasing_zip(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations) timeit.timeit('is_increasing_sorted(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations) timeit.timeit('is_increasing_starmap(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations) 

If the list was already monotonously increasing ( list_method == 1 ), the fastest and slowest was:

• sorted
• Starmap
• fine
• lightning

If the list was mostly monotonically increasing ( list_method == 2 ), the fastest for the slowest was:

• Starmap
• lightning
• fine
• sorted

(whether the bracket or zip was the fastest depends on the execution, and I could not identify the pattern. Starmap is usually faster)

If the list was completely random ( list_method == 3 ), the fastest and slowest was:

• Starmap
• lightning
• fine
• sorted (very bad)

Answer 8

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

Answer 9

This is possible with Pandas, which you can install through pip install pandas .

 import pandas as pd 

The following commands work with integer or floating point lists.

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 

Answer 10

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