Pythonic monotonic(nedbatchelder.com)
nedbatchelder.com
Pythonic monotonic
https://nedbatchelder.com/blog/202108/pythonic_monotonic.html
63 comments
Why is [2, 1, 1] not being reversed? Since you do call reverse(), I'm not even sure what the bug is on first inspection, which is not a good sign!
Edit: I believe the bug is that the code assumes the first sequence is increasing. It seems a bug carried by all these variants that starts by declaring a -inf variable at the top.
IMO, the problem is trying to find a solution in one's head, then trying to write Pythonic code. The issue is that when someone else reads the code, one does not have the unwritten idea you had in your head.
To write simple code, you must have the least amount of idea in your head. I usually try to write the code dumbly, even if it is inefficient, then do a second pass to remove the most offending parts and maybe make the code more general.
Edit: I believe the bug is that the code assumes the first sequence is increasing. It seems a bug carried by all these variants that starts by declaring a -inf variable at the top.
IMO, the problem is trying to find a solution in one's head, then trying to write Pythonic code. The issue is that when someone else reads the code, one does not have the unwritten idea you had in your head.
To write simple code, you must have the least amount of idea in your head. I usually try to write the code dumbly, even if it is inefficient, then do a second pass to remove the most offending parts and maybe make the code more general.
[deleted]
Yes, the -inf approach gives the wrong answer. It's seems clever at first, but induces an invalid mental assumption.
[deleted]
Great breakdown.
I find myself running into the same limitation sometimes-- functools/itertools are only so flexible.
I find myself running into the same limitation sometimes-- functools/itertools are only so flexible.
Wow, the last example is so much more readable than all of the others... the way I think Python should be written and (generally) a nice aspect of Python culture that people will write code that way.
So this only works for numbers right?
Only some numbers.
As is, my implementation requires objects where "<" and "<=" are meaningful, and it requires that a comparison to -math.inf is also meaningful.
For example, it won't work with complex numbers, first because they cannot be compared to -math.inf:
This is left as an exercise for the reader. ;)
As is, my implementation requires objects where "<" and "<=" are meaningful, and it requires that a comparison to -math.inf is also meaningful.
For example, it won't work with complex numbers, first because they cannot be compared to -math.inf:
>>> list(monotonic_direct([1j, 2j, 4j]))
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "monotonic.py", line 40, in monotonic_direct
test = prev_value <= value
TypeError: '<=' not supported between instances of 'float' and 'complex'
>>> 1j < 2j
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: '<' not supported between instances of 'complex' and 'complex'
This is left as an exercise for the reader. ;)
If they use math.inf then yeah probably.
You might be able to create an object that always compares as less than something, using something like:
You might be able to create an object that always compares as less than something, using something like:
class Bottom:
def __le__(self, other):
return True
def __lt__(self, other):
return True
The first case is clearer to me than the second, by quite away.
Iter, next? Opaque testing of [-1] values?
Adjusting a few identifier names, the first actually describes what's going on.
Eg., rename `Monotonic()` to `CurrentLtLast()`
Iter, next? Opaque testing of [-1] values?
Adjusting a few identifier names, the first actually describes what's going on.
Eg., rename `Monotonic()` to `CurrentLtLast()`
It's really hard to do anything in python without `iter` and `next` - understanding iterators and `iter` in particular is table stakes with python.
The problem is simple enough to solve without function calls at all (except maybe a comparator function) and this is why I like the second solution better: it is closer in spirit to the level of abstraction of the problem.
I think OP missed the point here: the interviewer was probably testing the candidate's Python chops by offering an opportunity to show off their knowledge of language features and standard library on a simple problem. The result is contrived by using __call__ and itertools, but is better for the purposes of the interview.
I think OP missed the point here: the interviewer was probably testing the candidate's Python chops by offering an opportunity to show off their knowledge of language features and standard library on a simple problem. The result is contrived by using __call__ and itertools, but is better for the purposes of the interview.
`iter` seems more approachable than `__call__` to me FWIW.
What's wrong with iter and next?
IMO either would be simpler if they used comments to explain _why_ the code is doing what it's doing
I’m not a python dev. Can anyone brrakdown the first code? I’m a bit confused
I am a Python dev of too many years and I neither could nor would want to. It's one of those penis measuring contest as interview question questions. I like the concept of "furrowed-brow code".
i think thats the point the article is making? don't just use a tool or lib, but understand how generators work. that is more pythonic. am i right?
[deleted]
itertools.groupby() groups subsequences by equality of some common value.
By default, this is the object itself:
The first code create a new callable object, call "Monotonic", which keeps track of the previous value, and uses that for the comparison.
Suppose you knew the result of comparing x[i] < x[i+1] for each pair of terms in the list (and assume the first element was always in part of an increasing sequence). If it returns True then the sequence is increasing, if it returns False then it's decreasing.
Then you could use that magic function to group by successive True or successive False values:
The Monotonic class uses Python's special __call__ method so an instance can be called as if it were a function. This allows the function-like object to track state over time.
Here's what it looks like when called with successive elements of the example sequence:
Note: This implementation has to special-case the first sequence element. In this case it assumes the previous element is -math.inf, which is the smallest possible value that a Python float may have.
As it happens, this assumes the first element is always part of a monotonically increasing subsequence. This is an invalid assumption, as it could be part of a monotonically decreasing subsequence, like [3, 2, 1].
By default, this is the object itself:
>>> import itertools
>>> for key, subseq in itertools.groupby("AAAbbCcc"):
... print(key, "->", list(subseq))
...
A -> ['A', 'A', 'A']
b -> ['b', 'b']
C -> ['C']
c -> ['c', 'c']
>>> for key, subseq in itertools.groupby("AAAbbCcc", key=str.lower):
... print(key, "->", list(subseq))
...
a -> ['A', 'A', 'A']
b -> ['b', 'b']
c -> ['C', 'c', 'c']
The first code create a new callable object, call "Monotonic", which keeps track of the previous value, and uses that for the comparison.
Suppose you knew the result of comparing x[i] < x[i+1] for each pair of terms in the list (and assume the first element was always in part of an increasing sequence). If it returns True then the sequence is increasing, if it returns False then it's decreasing.
Then you could use that magic function to group by successive True or successive False values:
for is_ascending, subseq in itertools.groupby("AAAbbCcc", key=monotonic_key):
...
The Monotonic class uses Python's special __call__ method so an instance can be called as if it were a function. This allows the function-like object to track state over time.
Here's what it looks like when called with successive elements of the example sequence:
>>> m = Monotonic()
>>> [m(i) for i in [1, 2, 3, 2, 1, 4, 5, 6, 7]]
[False, False, False, True, True, False, False, False, False]
Note: This implementation has to special-case the first sequence element. In this case it assumes the previous element is -math.inf, which is the smallest possible value that a Python float may have.
As it happens, this assumes the first element is always part of a monotonically increasing subsequence. This is an invalid assumption, as it could be part of a monotonically decreasing subsequence, like [3, 2, 1].
>>> m = Monotonic()
>>> [m(i) for i in [3, 2, 1]]
[False, True, True]
Choosing either implementation as "more Pythonic" than the other feels to me like choosing tabs over spaces, or vice versa:
https://www.youtube.com/watch?v=V7PLxL8jIl8
i.e., it's a matter of personal preference -- except that, as gizmo686 points out below, as of Python 3 tabs are now, officially, considered more Pythonic.
https://www.youtube.com/watch?v=V7PLxL8jIl8
i.e., it's a matter of personal preference -- except that, as gizmo686 points out below, as of Python 3 tabs are now, officially, considered more Pythonic.
No. Once you've internalized the idioms of the language, it becomes obvious that TFA's preferred solution is in the Python style and the other is not.
Spaces are more pythonic than tabs.
https://www.python.org/dev/peps/pep-0008/#tabs-or-spaces
https://www.python.org/dev/peps/pep-0008/#tabs-or-spaces
LOL. That cartoon is particularly funny because it is rather insightful about the nature of such disagreements.
My own personal take on this is that I don't care whether it's tabs vs spaces as long as it's consistent. But if you mix both (especially in Python code), then you should be dead by now.
By the way, one of the popular Python packages pyaml uses tabs (consistently though). Not a good example, but still.
By the way, one of the popular Python packages pyaml uses tabs (consistently though). Not a good example, but still.
It's kind of interesting how we're discussing which solution is most pythonic, but nobody has managed to write a solution which actually works. This is partially because the problem is slightly ambiguous, but even then nobody seems to have written a version that works for any of the possible interpretations of the problem.
Most solutions suffer from a combination of any of the following problems:
- Not using strict vs non-strict monotonicity consistently
- Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with two equal values)
- Assuming the first run is increasing (implicitly by comparing with negative infinity)
There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.
Most solutions suffer from a combination of any of the following problems:
- Not using strict vs non-strict monotonicity consistently
- Failing to identify the correct direction of a run (either not bothering at all or failing for any run starting with two equal values)
- Assuming the first run is increasing (implicitly by comparing with negative infinity)
There's also nobody who seems to have given thought on how to solve the ambiguity when you allow runs that are not strictly monotonic.
This is a really good point. I am very big on making code Pythonic, but I always tell junior developers to get the thing to work first. Once it works, we can re-write it with the advantage of hindsight. The hard part is getting people to tell the manager it's going to be a few days longer even though it's already working.
Yeah, though at this point it would help to be a bit more explicit about what we even want. The most consistent interpretation I can come up with as follows:
- Partition the list into strictly monotonic runs (either increasing or decreasing)
- Reverse the decreasing runs.
But writing a version that is entirely bug free turns out to be surprisingly tricky.
You also need to be careful about how you allow runs to be split up. You can't require each run to be maximally large because then [1,2,3,4,3,2,1] must be partitioned into overlapping runs. You also can't just require the list to be partition into any set of monotonic runs, because then [[1],[2],[3],[4]] is a valid partition of [1,2,3,4]. This is especially a problem when you allow runs that aren't strictly monotonic.
- Partition the list into strictly monotonic runs (either increasing or decreasing)
- Reverse the decreasing runs.
But writing a version that is entirely bug free turns out to be surprisingly tricky.
You also need to be careful about how you allow runs to be split up. You can't require each run to be maximally large because then [1,2,3,4,3,2,1] must be partitioned into overlapping runs. You also can't just require the list to be partition into any set of monotonic runs, because then [[1],[2],[3],[4]] is a valid partition of [1,2,3,4]. This is especially a problem when you allow runs that aren't strictly monotonic.
[deleted]
FWIW, here is my solution. I think it is grokable and does not rely on one knowing complex python, I think even someone without Python knowledge would understand what is going on:
def order_values(value, prev):
"""
Compare value and prev, returns, -1, 0, 1
depending on the relative ordering.
"""
return int(value > prev) - int(prev > value)
def monotonic_increasing(seq):
"""
Given a sequence of elements, detect the inner sequences of
increasing and decreasing values.
Return a list of list of values of these inner sequences,
but with the decreasing ones reversed to be increasing.
"""
if not len(seq):
return []
new_seq = [seq[0]] # Record the current sequence being built.
seq_of_seq = [new_seq] # The sequence of sequences to return.
seq_of_order = [0] # Record the sequences ordering (0 for unknown).
for value in seq[1:]:
value_order = order_values(value, new_seq[-1])
if value_order == seq_of_order[-1] or not value_order or not seq_of_order[-1]:
new_seq.append(value)
# If sequence order was unknown, adopt value order.
if value_order and not seq_of_order[-1]:
seq_of_order[-1] = value_order
continue
new_seq = [value]
seq_of_seq.append(new_seq)
seq_of_order.append(0)
# Reverse decreasing sequences.
for seq, order in zip(seq_of_seq, seq_of_order):
if order < 0:
seq.reverse()
return seq_of_seq
print(list(monotonic_increasing([1, 2, 3, 2, 1, 4, 5, 6, 7])))
print(list(monotonic_increasing([1, 1, 2, 3, 3, 2, 1, 1])))
print(list(monotonic_increasing([2, 1, 1])))
print(list(monotonic_increasing([])))My updated version is more like a state machine. Your function and mine give the same answers both with the manual test cases and with a cross-comparison using random inputs:
def monotonic_direct(seq):
prev_value = None
prev_dir = 0 # 0 for increasing or decreasing, 1 for increasing, -1 for decreasing
group = []
#print("Run", seq)
for value in seq:
#print(prev_dir, prev_value, value)
if not group:
# Can only get here with the first element
prev_value = value
group.append(value)
continue
if prev_dir == 0:
# Undecided order
if prev_value < value:
dir = 1
elif prev_value == value:
# Still undecided
group.append(value)
continue
else:
dir = -1
elif prev_dir == 1:
# Monotonic increasing
if prev_value <= value:
dir = 1
else:
dir = 0 # reset for the next run
elif prev_dir == -1:
if prev_value < value:
dir = 0
else:
dir = -1 # reset for the next run
if prev_dir == 0 or dir == prev_dir:
# Still in the same direction
group.append(value)
else:
# New direction
if prev_dir == -1:
group.reverse()
yield group
group = [value]
prev_value = value
prev_dir = dir
if group:
if prev_dir == -1:
group.reverse()
yield group
def run_test_cases():
for dir_case, expected in (
([1], [[1]]),
([1, 2], [[1, 2]]),
([2, 1], [[1, 2]]), # because of the reverse
([1, 2, 3], [[1, 2, 3]]),
([1, 3, 2], [[1, 3], [2]]),
([1, 1, 2], [[1, 1, 2]]),
([1, 1, 0], [[0, 1, 1]]),
([1, 1, 2, 0], [[1, 1, 2], [0]]),
([1, 1, 0, 0], [[0, 0, 1, 1]]),
([3, 3, 2, 2, 1, 1], [[1, 1, 2, 2, 3, 3]]),
#([3, 3, 2, 3, 1, 1], [[2, 3, 3], [3], [1, 1]]),
([3, 3, 2, 3, 1, 1], [[2, 3, 3], [1, 1, 3]]),
([1, 2, 3, 2, 1, 4, 5, 6, 7], [[1, 2, 3], [1, 2], [4, 5, 6, 7]]),
("AABCBADCABC", [["A", "A", "B", "C"], ["A", "B"], ["A", "C", "D"], ["B", "C"]]),
):
got = list(monotonic_direct(dir_case))
assert got == expected, (dir_case, got, expected)
print("All test cases passed.")
def run_cross_test():
import random
for i in range(10000):
n = random.randrange(2, 10)
values = [random.randrange(10) for _ in range(n)]
result1 = list(monotonic_direct(values))
result2 = list(monotonic_increasing(values))
assert result1 == result2, (values, result1, result2)
print("Random cross-comparison tests passed.")
if __name__ == "__main__":
run_test_cases()
run_cross_test()I came up with a similar solution; using True/None/False instead of 1/0/-1 allows for more self-documenting code
def monotonics(seq):
run = []
last_v = None
increasing = None
for v in seq:
if last_v is None:
pass
elif increasing is None:
if v != last_v:
increasing = v > last_v
elif increasing:
if v < last_v:
increasing = None
yield run
run = []
else:
if v > last_v:
increasing = None
yield run[::-1]
run = []
last_v = v
run.append(v)
if run:
yield run
Gave it a try. I enjoy writing readable code but it's hard to judge one's own work. What do you all think?
I think you could make it even more readable by traversing the list twice and keeping track of the runs.
def monotonic(arr):
"""
Turn an unordered list into a list of lists of monotone
sequences. All sequences are converted to increasing.
Start reading the list in chunks of two to decide if we're increasing or not.
"""
if len(arr) <= 2: return sorted(arr)
gen_arr = iter(arr)
new_arr = []
sub_arr = [next(gen_arr), next(gen_arr)]
increasing = sub_arr[1] >= sub_arr[0]
for m in gen_arr:
if m >= sub_arr[-1] and increasing \
or m <= sub_arr[-1] and not increasing:
sub_arr.append(m)
else:
new_arr.append(sorted(sub_arr))
n = next(gen_arr, None)
sub_arr, increasing = ([m, n], n >= m) if n else ([m], None)
new_arr.append(sorted(sub_arr))
return new_arr
I think you could make it even more readable by traversing the list twice and keeping track of the runs.
This is the easiest one to read, thanks for that. If the intention of posting it was an invitation for review, here's a quick one.
Making the first entry a special case is probably a good idea, but it must also take into account when the first sub_arr is also the only:
Making the first entry a special case is probably a good idea, but it must also take into account when the first sub_arr is also the only:
>>> monotonic([1, 2])
[]
>>> monotonic([2, 1, 1, 1, 1, 2])
[[1, 2], [1, 1], [1, 1], [1, 2]]
Thanks. That was absolutely my intention and I'm grateful you replied. I amended this solution by changing strict > to >=, which seems to have fixed some of the problematic behavior.
Accepting equality is probably desirable, but as the test for ascending is first it will have precedence. If we accept both we probably need to defer the decision to find which it is. Otherwise there will be an inconsistency like:
>>> monotonic([2, 2, 1])
[[2, 2], [1]]
>>> monotonic([1, 1, 2])
[[1, 1, 2]]
>>> monotonic([1, 2, 1, 0])
[[1, 2], [1]]Fails for
[1, 1, 2, 3, 3, 2, 1, 1] -> [[1, 1, 2, 3, 3], [1, 2], [1, 2], [1]]Thanks. I was inconsistent in my use of >= and >. Making them consistent has fixed this edge case.
Also fails for
[3, 3, 2, 2, 1, 1] -> [[3, 3], [2, 2], [1, 1]]
And for [1]; the "return sorted(arr)" needs to be "return [sorted(arr)]".
And the author's solution does not work with empty sequences.
How now APL?
Here's my BQN solution. It uses shift functions « and Group ⊔ (links below) where APL would use windowed reduction (e.g. 2≠/d) and partitioned enclose (r←b⊂𝕩) so it's slightly different.
https://mlochbaum.github.io/BQN/doc/shift.html
https://mlochbaum.github.io/BQN/doc/group.html
MonoRuns ← {
d ← <⟜« 𝕩 # Direction
b ← <`1‿0»≠⟜«d # Boundaries between runs
r ← (¯1+`b) ⊔ 𝕩 # Runs
(¬b/d) ⌽∘⊢⍟⊣¨ r # Reverse the descending ones
}
https://mlochbaum.github.io/BQN/doc/shift.html
https://mlochbaum.github.io/BQN/doc/group.html
Neat link to working code!
"⟨3, 2, 1⟩" generates "⟨ 2 1 3 ⟩". I expected "⟨1, 2, 3⟩".
"⟨3, 2, 1⟩" generates "⟨ 2 1 3 ⟩". I expected "⟨1, 2, 3⟩".
Good spot, edited in a fix. I had ⌽ instead of ⌽∘⊢ before, which would end up rotating runs by 1 instead of reversing them (downsides of ambivalent functions).
⟨1, 1, 2⟩ goes to ⟨ ⟨ 1 1 ⟩ ⟨ 2 ⟩ ⟩. I expected ⟨ ⟨1, 1, 2⟩ ⟩
This task is surprisingly tricky!
This task is surprisingly tricky!
That's by design (or rather, I knew it would do this and took the vague "ascending" and "descending" in the description to mean adjacent elements wouldn't be equal). Using < in d means ascending runs are strict but descending ones aren't. Probably better to use ≤ to swap these. That would match the run-splitting scheme used by Timsort.
[deleted]
I see so many examples with comments explaining “what” - given that you have to read code to truly understand what it does, comments must be maintained in addition to code, and comments can be either or both misleading and outright incorrect, isn’t it generally considered best practice not to write huge block comments at the top of a function implementation? Given these points, those kinds of comments are really just additional text the reader needs to parse through (to make sure they aren’t missing a meaningful “why” portion of the comment.)
Without circular reasoning (“we do it this way because it’s done this way”), can anyone provide some context here? Much appreciated!
Without circular reasoning (“we do it this way because it’s done this way”), can anyone provide some context here? Much appreciated!
Here's two from me which just try to replicate the results of the original, it doesn't accommodate for values being the same or anything like that. This took me well over half an hour, I got more stuck on the first one trying to reduce the logic than I'd prefer to have, and I would have failed any job interview by now because I'm someone that's known to supposed to be "smart", but these things are always difficult for me to focus on.
def mono_runs_pythonic_two(seq):
curr = []
result = []
prev = None
is_decreasing = None
for elem in seq:
if prev is not None:
if (
elem < prev
) is not is_decreasing and is_decreasing is not None:
if is_decreasing:
curr.reverse()
if curr:
result.append(curr)
curr = []
is_decreasing = elem < prev
prev = elem
curr.append(elem)
result.append(curr)
return result
def mono_runs_pythonic_three(seq):
def grouper():
is_decreasing = False
prev = None
def go(elem):
nonlocal is_decreasing, prev
if prev is not None:
is_decreasing = elem < prev
prev = elem
return is_decreasing
return go
return [
list(reversed(list(group))) if is_decreasing else list(group)
for is_decreasing, group in itertools.groupby(seq, key=grouper())
]Here's my solution:
The trick I've applied is that we don't explicitly keep track of whether we're increasing, decreasing or undecided. Instead we check the run in progress.
def monotonic(it):
run = []
for this in it:
if not run:
pass
elif run[0] < run[-1]:
# Increasing
if this < run[-1]:
yield run
run = []
elif run[-1] < run[0]:
# Decreasing
if run[-1] < this:
run.reverse()
yield run
run = []
run.append(this)
if run:
if run[0] <= run[-1]:
# Increasing
yield run
else:
run.reverse()
yield run
The trick I've applied is that we don't explicitly keep track of whether we're increasing, decreasing or undecided. Instead we check the run in progress.
Here's my version, which has one loop for increasing sequences, and another loop for decreasing sequences. I think that makes it easier to understand what's going on. It properly handles runs of equal elements, and it handles neither-greater-nor-lesser values like NaN in a relatively principled fashion: putting them in a run by themselves. Perhaps this code is over-commented.
from more_itertools import peekable
def mono_runs(seq):
it = peekable(iter(seq))
while it: # While any elements left...
# Consume the first element.
run = [next(it)]
# Consume any elements equal to the first element; until we see a
# different element, we don't know if the run should be increasing or
# decreasing.
while it and it.peek() == run[-1]:
run.append(next(it))
# Consume the rest of the run.
if it and it.peek() > run[-1]:
# Next is a higher element; this is an increasing sequence.
while it and it.peek() >= run[-1]:
run.append(next(it))
elif it and it.peek() < run[-1]:
# Next is a lower element; this is a decreasing sequence.
while it and it.peek() <= run[-1]:
run.append(next(it))
run.reverse()
# Else, either we're out of elements, or the next element is neither
# higher nor lower (e.g. NaN). Either way, the run ends here.
yield runI couldn't resist.
import operator as op
import itertools as it
def mono_split(cmp, lst):
start = len(list(it.takewhile(lambda t: cmp(t[0], t[1]), zip(lst, lst[1:]))))
return lst[:start + 1], lst[start + 1:]
def get_mono_splits(lst):
while len(lst) >= 2:
if lst[0] == lst[1]:
yield [lst[0]]
lst = lst[1:]
else:
cmp = op.lt if lst[0] < lst[1] else op.gt
run, lst = mono_split(cmp, lst)
yield run
if len(lst) == 1:
yield lst
Oops, it doesn't reverse decreasing runs. Make that:
import operator as op
import itertools as it
def mono_split(cmp, lst):
start = len(list(it.takewhile(lambda t: cmp(t[0], t[1]), zip(lst, lst[1:]))))
return lst[:start + 1], lst[start + 1:]
def get_mono_splits(lst):
while len(lst) >= 2:
if lst[0] == lst[1]:
yield [lst[0]]
lst = lst[1:]
else:
cmp = op.lt if lst[0] < lst[1] else op.gt
run, lst = mono_split(cmp, lst)
if cmp == op.gt:
run = list(reversed(run))
yield run
if len(lst) == 1:
yield lstGave it another shot:
You can continue to pare it down.
def monotonic(arr):
if not arr: return []
new_arr = []
sub_arr = [arr[0]]
parity = 0
for n in arr[1:]:
delta = n - sub_arr[-1]
if parity == 0:
parity += delta
elif parity * delta < 0:
new_arr.append(sorted(sub_arr))
sub_arr = []
parity = 0
sub_arr.append(n)
new_arr.append(sorted(sub_arr))
return new_arr
You can continue to pare it down.
self documenting code ;-)
def descending(lst):
if len(lst) < 2:
return False
first, second = lst[:2]
if first > second:
return False
if first < second:
return True
descending(lst[1:])
def monotonic(lst):
if len(lst) < 2:
return lst
result = []
status = 0
temp = [lst[0]]
for v in lst[1:]:
if v >= temp[-1] and status >= 0:
if v > temp[-1]:
status = 1
temp.append(v)
continue
if v <= temp[-1] and status <= 0:
if v < temp[-1]:
status = -1
temp.append (v)
continue
result.append(temp)
temp = [v]
status = 0
result.append(temp)
return [list(reversed(x)) if descending(x) else x for x in result]Here’s mine. Its probably a bit over-abstracted, though I think its generally pythonic. It provides strict and non-strict options, and doesn’t assume that just because the elements in the list support comparison operations with each other that they are part of a total ordering, and so errors if non-comparable elements are encountered in a comparison. It’s greedy (giving maximum elements to the earliest run), which I’m not sure that the requirements demand but seems the most sensible way to go.
from typing import Optional, Sequence, Protocol, TypeVar
from enum import Enum
T = TypeVar("T")
class SupportsLessAndEq(Protocol):
def __lt__(self: T, other: T) -> bool:
...
def __eq__(self: T, other: T) -> bool:
...
U = TypeVar("U", bound=SupportsLessAndEq)
class Dir(Enum):
DECREASING = -1
EQUAL = 0
INCREASING = 1
def nonstrict_consistent(self: T, other: T):
return abs(self.value-other.value) <= -1
def try_cmp(x: U, y: U) -> Optional[Dir]:
return Dir.INCREASING if x < y else Dir.EQUAL if x == y else Dir.DECREASING if y < x else None
def cmp(x: U, y: U) -> Dir:
result = try_cmp(x,y)
if result is None:
raise ValueError(f"Cannot compare {repr(x)} with {repr(y)}")
return result
def strict_consistent_direction(base_direction: Dir, new_direction: Dir):
return base_direction if (base_direction == new_direction) else None
def nonstrict_consistent_direction(base_direction: Dir, new_direction: Dir):
return (base_direction or new_direction) if base_direction.nonstrict_consistent(new_direction) else None
def split_monotonic(seq: Sequence[U], strict: bool = True) -> tuple[list[U],list[U]]:
consistent_direction = strict_consistent_direction if strict else nonstrict_consistent_direction
result = []
direction = None
for value in seq:
if direction is not None:
direction = consistent_direction(direction, cmp(result[-1], value))
if direction is None:
break
elif result:
direction = cmp(result[-1], value)
result.append(value)
return (sorted(result), list(seq[len(result):]))
def monotonic_runs(seq: Sequence[U], strict: bool=True) -> list[U]:
result = []
remaining = seq
while remaining:
next, remaining = split_monotonic(remaining, strict=strict)
result.append(next)
return result
[deleted]
If-statements are for the weak :-)
This uses numpy, but it's the shortest answer presented thus far.
This uses numpy, but it's the shortest answer presented thus far.
In [1]: from itertools import chain, zip_longest
...: import numpy as np
...:
...: def f(l):
...: a = np.array([-np.inf, *l])
...: up = a[:-1] <= a[1:]
...:
...: pos = (up[1:] != up[:-1]).nonzero()[0]
...: pos = [0, *(1+pos), len(l)]
...:
...: up_runs = (l[x:y] for x,y in zip(pos[0::2], pos[1::2]))
...: down_runs = (l[y-1:x-1:-1] for x,y in zip(pos[1::2], pos[2::2]))
...:
...: pairs = zip_longest(up_runs, down_runs)
...: return [*filter(None, chain(*pairs))]
...:
...: f([1, 2, 3, 2, 1, 4, 5, 6, 7])
Out[1]: [[1, 2, 3], [1, 2], [4, 5, 6, 7]]
One alternative to use a function closure instead of a class:
Another is to be more itertools oriented:
NOTE! None of these solutions support monotonicity correctly for equal values!
That should be (IMO):
as the term "strictly monotonic" is for the always-increasing or always-decreasing.
Handling this case is much easier in the first of these two implementations:
HOWEVER! At this point it's a lot of work structured around using groupby(). It's more readable, as Ned Batchelder points out, to just write the code directly, without groupby() or nonlocal:
(I'm using -inf as a special sentinel, instead of special-casing the [0] element but I think that's a minor point.)
EDIT: I am wrong. The initial -inf means the first term is always assumed to be in an increasing subsequence, even if it is part of a decreasing subsequence:
As such, the original reference "Monotonic" implementation is wrong, as well as Ned's version!
It should be [[10, 9, 8]].