Redistribution of numpy array with upper limit

Question

I`m currently struggling to write efficient function which will follow simple rules.

Lets assume matrix (it always came sorted descending).

| 7 4 3 2 |     # sums up to 16 
| 3 2 1 0 |     # sums up to 6

I want to clip values to certain number (let it be 5), but "rest" from clipping should propagate into columns to the right (these columns should be also clipped and so on). So having this in head, the result matrix should look like:

| 5 5 4 2 |     # still sums up to 16, but values "moves" to the right
| 3 2 1 0 |     # no value extends 5 do nothing happens

Algorithm isn't hard in terms in writing it with one loop (saving clipped values to buffer, distribute it in next column, and so on), which works well, but as I said, it would be ideal to make this using vectorization (and dismiss using any loop). I tried some cumsum + clip + diff solution, but nothing really works. Right now I`m stuck.

Thank you for any help.

The answer from the algorithm doesn't match the sample answer you specified. Can you please correct either of them? — ranka47
– ranka47, Commented Mar 20, 2020 at 21:45
Also, please clarify what is "rest" and what does "propagate to the right" means? — ranka47
– ranka47, Commented Mar 20, 2020 at 21:45

Alain T. · Accepted Answer · 2020-03-21 15:29:01Z

2

If you have many rows and not too many columns, you could approach it like this:

import numpy as np

def carry(sample,cap):
    result = sample.copy()
    for c in range(1,result.shape[1]):
        result[:,c] += np.maximum(result[:,c-1]-cap,0)
    result[:,:-1]  = np.minimum(result[:,:-1],cap)
    return result

output:

sample = np.array([[7, 4, 2,0], [3, 2, 1, 0]])
cap = 5

carry(sample,cap)

# [[5, 5, 3, 0],
   [3, 2, 1, 0]]

[EDIT] solution without loop

Although this may not leverage full vectorization (and runs slower), it does the trick without any loops:

def carry(sample,cap):
    fCarry = np.frompyfunc(lambda a,b:b+max(0,a-cap),2,1) 
    result = fCarry.accumulate(sample,dtype=np.object,axis=1)
    return np.minimum(cap,result.astype(sample.dtype))

Accumulate with the custom ufunc carries the extra amount(over the cap) to the next element. Then all the elements are brought down to the specified cap if they are over (their carry having already been transferred to the next neighbour)

edited Mar 21, 2020 at 15:29

answered Mar 21, 2020 at 0:39

Alain T.

42.2k4 gold badges36 silver badges57 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Łukasz Szymankiewicz Over a year ago

It id exacly what I was looking for! Thanks!

Collectives™ on Stack Overflow

Redistribution of numpy array with upper limit

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related