Python - How to check list monotonicity
PythonListPerformancePython Problem Overview
What would be an efficient and pythonic way to check list monotonicity?
i.e. 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
Python Solutions
Solution 1 - Python
It's better to avoid ambiguous terms like "increasing" or "decreasing" as it's not clear if equality is acceptable or not. You should always use either for example "non-increasing" (clearly equality is accepted) or "strictly decreasing" (clearly equality is NOT accepted).
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)
Solution 2 - Python
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.
Solution 3 - Python
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.
Solution 4 - Python
@6502 has the perfect code for lists, I just want to add a general 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))
Solution 5 - Python
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
Solution 6 - Python
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:]))
Solution 7 - Python
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
Solution 8 - Python
I timed all of the answers in this question under different conditions, and found that:
- Sorting was the fastest by a long shot IF the list was already monotonically increasing
- Sorting was the slowest by a long shot IF the list was shuffled/random or if the number of elements out of order was greater than ~1. The more out of order the list of course corresponds to a slower result.
- Michael J. Barbers method was the fastest IF the list was mostly monotonically increasing, or completely random.
Here is the code to try it out:
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 monotonically increasing (list_method == 1
), the fastest to slowest was:
- sorted
- starmap
- normal
- zip
If the list was mostly monotonically increasing (list_method == 2
), the fastest to slowest was:
- starmap
- zip
- normal
- sorted
(Whether or not the starmap or zip was fastest depended on the execution and I couldn't identify a pattern. Starmap appeared to be usually faster)
If the list was completely random (list_method == 3
), the fastest to slowest was:
- starmap
- zip
- normal
- sorted (extremely bad)
Solution 9 - Python
@6502 has elegant python code for this. Here is an alternative solution with simpler iterators and no potentially expensive temporary slices:
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 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 monotonic(L):
return non_increasing(L) or non_decreasing(L)
Solution 10 - Python
L = [1,2,3]
L == sorted(L)
L == sorted(L, reverse=True)
Solution 11 - Python
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 strict
ness. 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.
Solution 12 - Python
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 areTrue
- checking diffrence between first and last element for choosing comparison operator,
- using direct comparison
>=, <=
instead of calculatinnp.diff
,
Solution 13 - Python
Here are two ways of determining if a list if monotonically increasing or decreasing using just range
or list comprehensions. Using range is slightly more efficient because it can short-circuit, whereas the list comprehension must iterate over the entire list. Enjoy.
a = [1,2,3,4,5]
b = [0,1,6,1,0]
c = [9,8,7,6,5]
def monotonic_increase(x):
if len(x) <= 1: return False
for i in range(1, len(x)):
if x[i-1] >= x[i]:
return False
return True
def monotonic_decrease(x):
if len(x) <= 1: return False
for i in range(1, len(x)):
if x[i-1] <= x[i]:
return False
return True
monotonic_increase = lambda x: len(x) > 1 and all(x[i-1] < x[i] for i in range(1, len(x)))
monotonic_decrease = lambda x: len(x) > 1 and all(x[i-1] > x[i] for i in range(1, len(x)))
print(monotonic_increase(a))
print(monotonic_decrease(c))
print(monotonic_decrease([]))
print(monotonic_increase(c))
print(monotonic_decrease(a))
print(monotonic_increase(b))
print(monotonic_decrease(b))
Solution 14 - Python
def solution1(a):
up, down = True, True
for i in range(1, len(a)):
if a[i] < a[i-1]: up = False
if a[i] > a[i-1]: down = False
return up or down
def solution2(a):
return a == sorted(a[::-1])
Solution1 is O(n) and the shorter solution2 is O(n log n)
Solution 15 - Python
>>> seq = [0, 1, 2, 3, 3, 4]
>>> seq == sorted(seq) or seq == sorted(seq, reverse=True)