matrix: move n-th row by n position efficiently

Question

I have a numpy 2d array and I need to transform it in a way that the first row remains the same, the second row moves by one position to right, (it can wrap around or just have zero padded to the front). Third row shifts 3 positions to the right, etc. I can do this through a "for loop" but that is not very efficient. I am guessing there should be a filtering matrix that multipled by the original one will have the same effect, or maybe a numpy trick that will help me doing this? Thanks! I have looked into numpy.roll() but I don't think it can work on each row separately.

import numpy as np
p = np.array([[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]])
'''
p = [ 1   2   3   4
      5   6   7   8
      9   10  11  12
      13  14  15  16]
desired output:
p'= [ 1   2   3   4
      0   5   6   7
      0   0   9   10
      0   0   0   13]
'''

Answer 1

We can extract sliding windows into a zeros padded version of the input to have a memory efficient approach and hence performant too. To get those windows, we can leverage np.lib.stride_tricks.as_strided based scikit-image's view_as_windows. More info on use of as_strided based view_as_windows.

Hence, the solution would be -

from skimage.util.shape import view_as_windows

def slide_by_one(p):
    m,n = p.shape
    z = np.zeros((m,m-1),dtype=p.dtype)
    a = np.concatenate((z,p),axis=1)
    w  = view_as_windows(a,(1,p.shape[1]))[...,0,:]
    r = np.arange(m)
    return w[r,r[::-1]]

Sample run -

In [60]: p # generic sample of size mxn
Out[60]: 
array([[ 1,  5,  9, 13, 17],
       [ 2,  6, 10, 14, 18],
       [ 3,  7, 11, 15, 19],
       [ 4,  8, 12, 16, 20]])

In [61]: slide_by_one(p)
Out[61]: 
array([[ 1,  5,  9, 13, 17],
       [ 0,  2,  6, 10, 14],
       [ 0,  0,  3,  7, 11],
       [ 0,  0,  0,  4,  8]])

We can leverage the regular rampy pattern to have a more efficient approach with a more raw usage of np.lib.stride_tricks.as_strided, like so -

def slide_by_one_v2(p):
    m,n = p.shape
    z = np.zeros((m,m-1),dtype=p.dtype)
    a = np.concatenate((z,p),axis=1)
    s0,s1 = a.strides
    return np.lib.stride_tricks.as_strided(a[:,m-1:],shape=(m,n),strides=(s0-s1,s1))

Another one with some masking -

def slide_by_one_v3(p):
    m,n = p.shape
    z = np.zeros((len(p),1),dtype=p.dtype)
    a = np.concatenate((p,z),axis=1)
    return np.triu(a[:,::-1],1)[:,::-1].flat[:-m].reshape(m,-1)

Answer 2

Here is a simple method based on zero-padding and reshaping. It is fast because it avoids advanced indexing and other overheads.

def pp(p):
    m,n = p.shape
    aux = np.zeros((m,n+m-1),p.dtype)
    np.copyto(aux[:,:n],p)
    return aux.ravel()[:-m].reshape(m,n+m-2)[:,:n].copy()