Python: Are Terms in this List Monotonic?

  • Thread starter WWGD
  • Start date
  • #1
WWGD
Science Advisor
Gold Member
5,561
4,604
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:

Answers and Replies

  • #2
Baluncore
Science Advisor
9,421
3,900
Compute a list of the n-1 differences.
Check if the sign of the differences ever changes.
Is a zero real positive or negative?
 
  • #3
WWGD
Science Advisor
Gold Member
5,561
4,604
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
Baluncore
Science Advisor
9,421
3,900
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
WWGD
Science Advisor
Gold Member
5,561
4,604
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
Baluncore
Science Advisor
9,421
3,900
But you must not multiply zeros, you must skip them, since they can allow the sign of the difference to flip.
 
  • #7
35,129
6,876
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.
 
  • #8
Ibix
Science Advisor
Insights Author
2020 Award
8,128
7,451
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.
 
  • #9
pbuk
Science Advisor
Gold Member
2,352
1,088
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
Svein
Science Advisor
Insights Author
2,176
711
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
pbuk
Science Advisor
Gold Member
2,352
1,088
  • If a2=a1 then not monotonic.
No, we are not looking for strict monotonicity.
 
  • #12
Baluncore
Science Advisor
9,421
3,900
No, we are not looking for strict monotonicity.
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
pbuk
Science Advisor
Gold Member
2,352
1,088
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
WWGD
Science Advisor
Gold Member
5,561
4,604
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
WWGD
Science Advisor
Gold Member
5,561
4,604
Now even I am not strictly non-confused.
Ok, my bad, let's do just non decreasing/increasing for both.
 
  • #16
pbuk
Science Advisor
Gold Member
2,352
1,088
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
Baluncore
Science Advisor
9,421
3,900
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.
 
  • #18
pbuk
Science Advisor
Gold Member
2,352
1,088
Deleted: going back to reread the OP!
 
Last edited:
  • #19
pbuk
Science Advisor
Gold Member
2,352
1,088
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?

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

,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.)

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!

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

Ok, my bad, let's do just non decreasing/increasing for both.
And now you are confirming you dont 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
2,078
178
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:
  • #21
Baluncore
Science Advisor
9,421
3,900
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
Ibix
Science Advisor
Insights Author
2020 Award
8,128
7,451
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.
 
  • #23
2,078
178
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
 
  • #24
263
120
When you got it working for longer lists think about what should happen if the list has zero or one element. :wink:
 
  • #25
pbuk
Science Advisor
Gold Member
2,352
1,088
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?
 

Related Threads on Python: Are Terms in this List Monotonic?

  • Last Post
Replies
15
Views
845
Replies
9
Views
860
Replies
3
Views
866
Replies
3
Views
716
  • Last Post
Replies
4
Views
651
Replies
3
Views
645
  • Last Post
Replies
11
Views
868
Replies
6
Views
5K
Replies
7
Views
1K
Top