Python: Are Terms in this List Monotonic?

In summary: We are working with real numbers, so I assumed that duplicates were as acceptable as a one LSB difference in any floating point representation. The critical thing being that it does not flip the sign of the difference.In summary,The program detects the first non-zero difference in a list of Real numbers, and compares that difference with all the following differences. If the list fails the test for monotonicity, the program returns a no.
  • #1
WWGD
Science Advisor
Gold Member
6,910
10,288
TL;DR Summary
Given a list of Real numbers in Python , how do we tell if its terms are monotonic,i.e., if they are in strictly non-decreasing or strictly non-increasing order. I know how to do either one; either strictly increasing,strictly decreasing or both.
Given a list [ a,b,c,..., z] in Python, write a program to determine if the terms are monotonic or not. I can do either , and combine theminto a long, clunky program, but trying to see if I can find a succint way of doing both. I have heard that using ' Nums' may do it,but it seems too high-level for my taste.

For, say, non-decreasing we can do something like :

Python:
List=L=[ a1, a2,...,an]
for i in in range(length(L)):
if L[i+1]-L[i] >=0:
return(' Yes,list is monotonic non-decreasing')
else:
print('No,not monotonic' non-decreasing)
Similar for non-increasing.
And maybe I can do a kludge to join the code for both.
Someone suggested I look up 'Nums'.I did and it looks a bit high-level ( i.e., black-boxed').
Any idea to cover both cases in a single program?[/i][/code]
 
Last edited by a moderator:
Technology news on Phys.org
  • #2
Compute a list of the n-1 differences.
Check if the sign of the differences ever changes.
Is a zero real positive or negative?
 
  • Like
Likes WWGD
  • #3
Baluncore said:
Compute a list of the n-1 differences.
Check if the sign of the differences ever changes.
Integers or reals? Is zero positive or negative?
Thanks: Yes, what I do is I loop from 1 to length of the list and test wether (i+i)st -ith item is larger or equal to zero if list is L, then check if L[i+1]-L >=0. But this works for either monotone decreasing or monotone increasing and I am not sure how to integrate both into a single program/algorithm.
 
  • #4
You only need detect the first change of sign.
Find the first non-zero difference, then compare that with all following differences. If you multiply two adjacent differences and the result is < zero then the list fails the test.
 
  • Like
Likes Vanadium 50, Wrichik Basu and WWGD
  • #5
Baluncore said:
You only need detect the first change of sign.
Find the first non-zero difference, then compare that with all following differences. If you multiply two adjacent differences and the result is < zero then the list fails the test.
Cool, so I can then iterate over all products LxL[i+1] and if I detect one negative, I return a no, other
ways I conclude it's monotone. Thanks, nice job.
 
  • #6
But you must not multiply zeros, you must skip them, since they can allow the sign of the difference to flip.
 
  • Like
Likes WWGD
  • #7
Baluncore said:
Is a zero real positive or negative?
It could be either. The IEEE 754 specification of floating point numbers has separate representations for -0 and +0. Most programming languages these days adhere to this specification as far as floating point reals are concerned.
 
  • Informative
Likes anorlunda
  • #8
Loops in python tend to be quite slow. I'd suspect it would be faster (possibly a lot faster) to use list comprehensions and the cmp() and any() or all() functions to get the signs of the differences and a summary of those signs.
 
  • Like
Likes pasmith
  • #9
How's it going? Does your answer look anything like mine?
Python:
from functools import reduce

# myList = [ ... ]

isIncreasing, isDecreasing, _ = reduce(
    lambda s, el: [s[0] and el >= s[2], s[1] and el <= s[2], el],
    myList,
    [True, True, myList[0]]
)

# Show whether increasing, decreasing, constant (T, T) or none (F, F).
print(isIncreasing, isDecreasing)

# Just show True iff loosely monotonic (including constant).
print(isIncreasing or isDecreasing)
 
Last edited:
  • #10
Just check the first two:
  • If a2<a1 check if the rest is descending.
  • If a2=a1 then not monotonic.
  • If a2>a1 check if the rest is ascending.
 
  • #11
Svein said:
  • If a2=a1 then not monotonic.
No, we are not looking for strict monotonicity.
 
  • #12
pbuk said:
No, we are not looking for strict monotonicity.
WWGD said:
Summary:: Given a list of Real numbers in Python , how do we tell if its terms are monotonic,i.e., if they are in strictly non-decreasing or strictly non-increasing order. I know how to do either one; either strictly increasing,strictly decreasing or both.
Now even I am not strictly non-confused.
 
  • Like
  • Haha
Likes Vanadium 50 and pbuk
  • #13
Baluncore said:
Now even I am not strictly non-confused.
To be fair Mathworld, as well as Wikipedia use similar confusing definitions. I was working on the basis that the use of the >= test rather than > in posts #1 and #3 made it clear that we were not looking for strictness.
 
  • #14
Baluncore said:
But you must not multiply zeros, you must skip them, since they can allow the sign of the difference to flip.
I thought of recursively applying the min to the list: If L[1] is the min, L[2] is the min of the remaining terms, etc.
 
  • #15
Baluncore said:
Now even I am not strictly non-confused.
Ok, my bad, let's do just non decreasing/increasing for both.
 
  • #16
WWGD said:
Ok, my bad, let's do just non decreasing/increasing for both.
That's still confusing: 'strictly increasing' is a lot easier to parse than 'non decreasing', and 'strictly monotonic' is certainly easier than 'non-(decreasing/increasing)'.

Have you got anything working yet - I could see a few problems in your first post?
 
  • #17
pbuk said:
I was working on the basis that the use of the >= test rather than > in posts #1 and #3 made it clear that we were not looking for strictness.
We are working with real numbers, so I assumed that duplicates were as acceptable as a one LSB difference in any floating point representation. The critical thing being that it does not change direction.
 
  • Like
Likes pbuk
  • #18
Deleted: going back to reread the OP!
 
Last edited:
  • #19
WWGD said:
Given a list of Real numbers in Python
There is no such thing as a list of real numbers in Python: we can have a list of floats though, is this what you mean?

WWGD said:
how do we tell if its terms are monotonic
By this I assume you don't mean strictly monotonic...

WWGD said:
,i.e., if they are in strictly non-decreasing or strictly non-increasing order.
... and this confirms that you don't mean strictly monotonic (strictly non-decreasing is the same as non-strictly increasing etc.)

WWGD said:
I know how to do either one; either strictly increasing,strictly decreasing or both.
But now you are testing for strict monotonicity which is not what you want!

WWGD said:
Python:
if L[i+1]-L[i] >=0:
But this test does not give you strictly increasing because equal values pass!

WWGD said:
Ok, my bad, let's do just non decreasing/increasing for both.
And now you are confirming you don't want strictness!

Probably best to leave this horrible confusion and start again if you are still interested. Note however that if this is another interview question the interviewer could be more interested in a discussion about the advantages and disadvantages of solving it with a loop rather than a reduce as I did, or a combination of list comprehensions as somebody else suggested rather than the actual coding of a working solution, which ought to be pretty easy.
 
Last edited:
  • #20
WWGD said:
Summary:: Given a list of Real numbers in Python , how do we tell if its terms are monotonic,i.e., if they are in strictly non-decreasing or strictly non-increasing order. I know how to do either one; either strictly increasing,strictly decreasing or both.

Given a list [ a,b,c,..., z] in Python, write a program to determine if the terms are monotonic or not. I can do either , and combine theminto a long, clunky program, but trying to see if I can find a succint way of doing both. I have heard that using ' Nums' may do it,but it seems too high-level for my taste.

For, say, non-decreasing we can do something like :

Python:
List=L=[ a1, a2,...,an]
for i in in range(length(L)):
if L[i+1]-L[i] >=0:
return(' Yes,list is monotonic non-decreasing')
else:
print('No,not monotonic' non-decreasing)
Similar for non-increasing.
And maybe I can do a kludge to join the code for both.
Someone suggested I look up 'Nums'.I did and it looks a bit high-level ( i.e., black-boxed').
Any idea to cover both cases in a single program?[/i][/code]

Try this. I think its pretty clear and fast.

Python:
def is_monotonic(xlist):
    xlist_sorted_inc = sorted(xlist)
    xlist_sorted_dec = sorted(xlist)[::-1]
    if xlist == xlist_sorted_inc or  xlist == xlist_sorted_dec:
        return 'monotonic'
    return 'not monotonic'
 
Last edited:
  • Like
Likes WWGD
  • #21
Here is a non-python fast algorithm that uses one loop, written in VB pseudocode.
VB:
' test list of floats for monotonicity, duplicates are OK.

Const As Integer n = 5
Dim As Double a( 1 To n ) = { 1, 1, 2, 2, 1 }   ' a list

Dim As Boolean mono_flag = True
Dim As Double diff, last_diff = 0
For i As Integer = 2 To n
    diff = a( i - 1 ) - a( i )
    If diff <> 0 Then   ' not a duplicate
        If ( diff * last_diff ) < 0 Then    ' sign changed
            mono_flag = False
            Exit For    ' may as well quit
        End If
        last_diff = diff
    End If
Next i

' report result
If mono_flag Then
    Print " monotonic pass "
Else
    Print " fails test"
End If
 
  • #22
Arman777 said:
Try this. I think its pretty clear and fast.

Python:
def is_monotonic(xlist):
    xlist_sorted_inc = sorted(xlist)
    xlist_sorted_dec = sorted(xlist)[::-1]
    if xlist == xlist_sorted_inc or  xlist == xlist_sorted_dec:
        return 'not monotonic'
    return 'monotonic'
Isn't the logic flipped here? If the list is equal to a sorted copy then it's monotonic.
 
  • Like
Likes Arman777
  • #23
Ibix said:
Isn't the logic flipped here? If the list is equal to a sorted copy then it's monotonic.
Yes, sorry. I kind of mixed the definition of 'monotonic'. I fixed it
 
  • Like
Likes Ibix
  • #24
When you got it working for longer lists think about what should happen if the list has zero or one element. :wink:
 
  • #25
Arman777 said:
Python:
def is_monotonic(xlist):
    xlist_sorted_inc = sorted(xlist)
    xlist_sorted_dec = sorted(xlist)[::-1]
    if xlist == xlist_sorted_inc or  xlist == xlist_sorted_dec:
        return 'monotonic'
    return 'not monotonic'
Questions:
  1. Do you know another way to do sorted(xlist)[::-1]?
  2. If so, why did you choose that way?
  3. You create the descending list immediately after creating the ascending list. Can you think of something else you could do first?
  4. Is 'monotonic' the kind of return value you would normally expect from a function called is_monotonic()?
  5. Can you think of a situation where sorting a list to see if it is monotonic might not be a good idea?
 
  • #26
pbuk said:
Do you know another way to do sorted(xlist)[::-1]?
yes
pbuk said:
If so, why did you choose that way?
theres no reason.
pbuk said:
Is 'monotonic' the kind of return value you would normally expect from a function called is_monotonic()?
You can return True or False as well.
pbuk said:
Can you think of a situation where sorting a list to see if it is monotonic might not be a good idea?
I don't know...
 
  • #27
Arman777 said:
.
I don't know...

Efficiency is often overrated, but what is the asymptotic time it takes to run your algorithm, vs something that just goes through the list twice to check each form of monotonicity?
 
  • #28
Sorting a list is O(n log n). Checking a list once is O(n).
Avoid sorting long lists, twice.
Python:
def is_monotonic( a: float ) -> bool:
    last_diff = 0.0
    for i in range( 1, len( a ) ):
        diff = a[ i-1 ] - a[ i ]
        if diff != 0.0:         # is not a duplicate
            if ( diff * last_diff ) < 0.0:
                return False    # diff changed sign
            last_diff = diff
    return True

a = [ 3, 2, 2, -1, -1 ]         # a list
print( a, is_monotonic( a ) )
 
Last edited:
  • Like
Likes Arman777
  • #29
Office_Shredder said:
Efficiency is often overrated, but what is the asymptotic time it takes to run your algorithm, vs something that just goes through the list twice to check each form of monotonicity?
If I am not mistaken its in the order ##O(n)##.
 
  • #30
Office_Shredder said:
Efficiency is often overrated, but what is the asymptotic time it takes to run your algorithm, vs something that just goes through the list twice to check each form of monotonicity?
You only need to scan the list once if you test for a sign change of the first difference.
If you use sort you must do it twice, once for ascending and once for descending.
But with Python the aim is to write the minimum source code, in a way that can be quickly understood. Sorting twice will win under that measure.

A monotonicity test is not the type of algorithm I would expect to find inside a tight loop, or running 50,000 times each day. If you only run the test once each day, on a 100 element list, then efficiency is irrelevant.
 
  • #31
Baluncore said:
You only need to scan the list once if you test for a sign change of the first difference.
If you use sort you must do it twice, once for ascending and once for descending.
Yes, and even if the algorithm used is ## O(n \log n) ## then in practice performance is much worse than ## k n \log n ## because there is a step change in ## k ## when the list no longer fits in processor cache, and again, dramitcally when the list no longer fits in main memory. There is also the memory usage to consider.

Baluncore said:
But with Python the aim is to write the minimum source code, in a way that can be quickly understood.
Even if "minimum source code" were a criterion (and I don't see that anywhere in the question) I don't think it would ever be the only criterion without any regard to performance.

Baluncore said:
Sorting twice will win under that measure.
But it will lose against an equally or even more concise implementation of a list traversal such as the one in #9.

Baluncore said:
A monotonicity test is not the type of algorithm I would expect to find inside a tight loop, or running 50,000 times each day. If you only run the test once each day, on a 100 element list, then efficiency is irrelevant.
No list length was specified in the op. Edit: I agree that premature optimization is to be avoided, but selecting an (at best) ## O(n \log n) ## time ## O(n) ## memory implementation when there is an at least equally trivial ## O(n) ## time ## O(1) ## memory one available is premature pessimization, and this is never good.
 
  • #32
Since we all seem to be posting solutions, here's what I had in mind:
Python:
MONOTONIC_INCREASING=1
MONOTONIC_DECREASING=-1
NOT_MONOTONIC=0

def isMonotonic(lst):
    ordered=[cmp(l1,l) for (l,l1) in zip(lst[:-1],lst[1:]) if cmp(l,l1)!=0]
    if len(ordered)==0 or all(o==1 for o in ordered):
        return MONOTONIC_INCREASING
    if all(o==-1 for o in ordered):
        return MONOTONIC_DECREASING
    return NOT_MONOTONIC
The cmp ("compare") function returns 1, 0, or -1 depending on whether the first argument is greater than, equal to, or less than the second, and it's used with zip to get a list of each element compared to the next, dropping equalities. Then it just checks that all differences were positive (or all elements were equal, arbitrarily) or all negative.
 
  • #33
Ibix said:
The cmp ("compare") function returns 1, 0, or -1 depending on whether the first argument is greater than, equal to, or less than the second
Only in Python 2: it does not exist in Python 3, although it is easy enough to implement. Also I believe your algorithm checks strict monotonicity, the OP (or a later clarification) asked for a loose check.
 
  • #34
pbuk said:
Only in Python 2: it does not exist in Python 3
Spot the person with the elderly python install. In that case, try
Python:
ordered=[(1 if l1>l else -1) for (l,l1) in zip(lst[:-1],lst[1:]) if l!=l1]
(I think I have the comparison the right way round).
pbuk said:
Also I believe your algorithm checks strict monotonicity, the OP (or a later clarification) asked for a loose check.
I don't think so. It drops the cases where they are equal, so [1,2,2,3] should give [1,1,1], which I think matches the loose check criterion.
 
  • #35
Ibix said:
It drops the cases where they are equal, so [1,2,2,3] should give [1,1,1], which I think matches the loose check criterion.
Ah yes, didn't see that (and I couldn't check because I am not running Py2 which is now 18 months past EOL!)
 
<h2>1. What is Python and why is it used in science?</h2><p>Python is a high-level, interpreted programming language that is widely used in scientific research and data analysis. It is known for its simple syntax, versatility, and powerful libraries that make it easy to perform complex tasks.</p><h2>2. What does it mean for terms in a list to be monotonic?</h2><p>A monotonic list is one where the terms either consistently increase or consistently decrease in value as you move through the list. This means that there is a clear trend or pattern in the data, and it can be useful for analyzing relationships between variables.</p><h2>3. How can I check if a list is monotonic in Python?</h2><p>You can use the <code>all()</code> function in Python to check if a list is monotonic. This function takes in an iterable object, such as a list, and returns <code>True</code> if all elements in the list evaluate to <code>True</code>. In the case of a monotonic list, this means that all elements must either be increasing or decreasing in value.</p><h2>4. What are some applications of analyzing monotonic lists in science?</h2><p>Monotonic lists can be useful for identifying trends in data, making predictions, and understanding relationships between variables. They are commonly used in fields such as statistics, economics, and biology to analyze data and make informed decisions based on the patterns observed.</p><h2>5. Can a list be both monotonic and non-monotonic?</h2><p>No, a list cannot be both monotonic and non-monotonic. A list is either monotonic or it is not. However, a list can have sections that are monotonic and other sections that are not, depending on the data and the specific trends being analyzed.</p>

1. What is Python and why is it used in science?

Python is a high-level, interpreted programming language that is widely used in scientific research and data analysis. It is known for its simple syntax, versatility, and powerful libraries that make it easy to perform complex tasks.

2. What does it mean for terms in a list to be monotonic?

A monotonic list is one where the terms either consistently increase or consistently decrease in value as you move through the list. This means that there is a clear trend or pattern in the data, and it can be useful for analyzing relationships between variables.

3. How can I check if a list is monotonic in Python?

You can use the all() function in Python to check if a list is monotonic. This function takes in an iterable object, such as a list, and returns True if all elements in the list evaluate to True. In the case of a monotonic list, this means that all elements must either be increasing or decreasing in value.

4. What are some applications of analyzing monotonic lists in science?

Monotonic lists can be useful for identifying trends in data, making predictions, and understanding relationships between variables. They are commonly used in fields such as statistics, economics, and biology to analyze data and make informed decisions based on the patterns observed.

5. Can a list be both monotonic and non-monotonic?

No, a list cannot be both monotonic and non-monotonic. A list is either monotonic or it is not. However, a list can have sections that are monotonic and other sections that are not, depending on the data and the specific trends being analyzed.

Similar threads

  • Programming and Computer Science
Replies
4
Views
924
Replies
6
Views
515
  • Programming and Computer Science
Replies
4
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
2
Views
624
  • Programming and Computer Science
Replies
3
Views
255
  • Programming and Computer Science
Replies
10
Views
2K
  • Programming and Computer Science
Replies
3
Views
658
Replies
9
Views
904
  • Programming and Computer Science
Replies
1
Views
692
Back
Top