Pythonic monotonic

Re:Pythonic monotonic by pierrebai on Friday August 13, 2021 @10:05AM (#28168975)

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([])))

[ Parent | on HN ]

Re:Pythonic monotonic by eesmith on Friday August 13, 2021 @10:41AM (#28169477)

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()

[ Parent | on HN ]

Re:Pythonic monotonic by klyrs on Friday August 13, 2021 @03:31PM (#28173469)

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

and, I'd add a two more test cases: [], and [1, 2, 3, 1, 2, 3]

[ Parent | on HN ]