Isotonic PAVA One Merge

Problem

Fit an isotonic (non-decreasing) regression with the pool-adjacent-violators algorithm.

Process the values left to right, merging adjacent blocks whenever a block value exceeds the next one; a merged block takes the size-weighted average of its members. Return the fitted values with the same length as the input; an empty input returns [].

Hint

Keep merging backwards while the previous block violates monotonicity.

Test cases

case 1

in: [[1,3,2,4]]

expected: [1,2.5,2.5,4]

case 2

in: [[5,4,3,2]]

expected: [3.5,3.5,3.5,3.5]

case 3

in: [[1,2,3]]

expected: [1,2,3]

case 4

in: [[]]

expected: []

case 5

in: [[2]]

expected: [2]

Starter codePython

def isotonic_pava(y):
    # Your code here
    pass

5 test cases · run your code against them in the editor