Reputation:
Reverse (flip) right-left(anti-)diagonals of a non-square numpy array
What I am after is Python code able to reverse the order of the values in each of the array anti-diagonals in a numpy array.
I have already tried various combinations of np.rot90, np.fliplr, np.transpose, np.flipud but none is able to give me the original shape of the 5x3 array with all the anti-diagonals reversed.
Any idea how to accomplish this?
Example:
[[ 1 2 4]
[ 3 5 7]
[ 6 8 10]
[ 9 11 13]
[12 14 15]]
Should become:
[[ 1 3 6]
[ 2 5 9]
[ 4 8 12]
[ 7 11 14]
[10 13 15]]
I suppose it must be easy, but somehow I have yet failed to find how to do it efficiently on arrays with millions of values.
Inspired by the already provided answers (status 2024-05-23 11:37 CET) and re-thinking what would be the most efficient way of getting the required transformation done it seems that giving a simple function taking two indices : iRow, jColumn of a value in an array and returning the required i,j indices to access the array as if it were flipped/reversed over the diagonals will provide fastest results. With such function for the over the diagonals flipped version of the array would be getting the right values without operating on the array as easy as in a trivial case of one-based and column/row based access to array values demonstrated below:
import numpy as np
srcArr = np.array([[ 1, 2, 3, 4, 5, 6],
[ 7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24]])
def ijOfArrayValueGivenOneBasedColumnRowBasedIndices(i, j):
return ( j - 1, i - 1 )
print( srcArr[
ijOfArrayValueGivenOneBasedColumnRowBasedIndices(
3,4)] ) # gives 21
print( srcArr[3,4] ) # gives 23
From this perspective the question comes down to providing a function
ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt(i,j,arrShapeRows,arrShapeColumns)
Upvotes: 9
Views: 1046
Answers (16)
Reputation: 10474
Solution
Swapping i and j but offsetting each diagonal as needed:
def mirror(a):
m, n = a.shape
i, j = np.indices(a.shape)
d = i+j+1
o = np.fmin(d, n) - np.fmin(d, m)
return a[j-o, i+o]
(See revision 6 for variations, not sure what's best. I picked the shortest now.)
Explanation
Let's say you have a 3×5 matrix. Consider its diagonals:
If we just swap i and j, we get this:
The first three diagonals are correct, but the later ones are outside the matrix. We need to offset (upwards and rightwards) the first bad diagonal by 1 and the others by 2 so that they're correctly in the matrix:
Note that i+j identifies the diagonal. For example a[0,3] and a[2,1] are on the same diagonal, since 0+3=2+1. As long as i+j is less than m and n, that diagonal doesn't need offsetting. But as soon as the smaller of m and n is reached, we need to offset each diagonal by one more position than the previous, until i+j reaches the larger of m and n. From then on, the offset remains the same.
Demo / tests
import numpy as np
for m, n in (5, 3), (4, 6):
a = np.arange(m*n).reshape((m, n))
print(a)
print('->')
print(mirror(a))
print()
Output (Attempt This Online!, includes more testing):
[[ 0 1 2]
[ 3 4 5]
[ 6 7 8]
[ 9 10 11]
[12 13 14]]
->
[[ 0 3 6]
[ 1 4 9]
[ 2 7 12]
[ 5 10 13]
[ 8 11 14]]
[[ 0 1 2 3 4 5]
[ 6 7 8 9 10 11]
[12 13 14 15 16 17]
[18 19 20 21 22 23]]
->
[[ 0 6 12 18 19 20]
[ 1 7 13 14 15 21]
[ 2 8 9 10 16 22]
[ 3 4 5 11 17 23]]
ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt
My version of the function requested at the bottom of the question. If arguments i and j are single ints, then min suffices. I kept np.fmin so it can also be used for whole index arrays, as shown in the below mirror function.
# The requested function
def ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt(i,j,arrShapeRows,arrShapeColumns):
d = i + j
o = np.fmin(d, arrShapeRows-1) - np.fmin(d, arrShapeColumns-1)
return j+o, i-o
# Applying the function to the whole array
def mirror(a):
ijFunc = ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt
return a[ijFunc(*np.indices(a.shape), *a.shape)]
Upvotes: 5
Reputation: 7260
Obtaining and flipping diagonals by slicing a flattened array
Produce a slice to get positions of an anti-diagonal items based on a diagonal offset and an array shape:
def antidiagonal_slice(offset, height, width):
if offset < width:
start = offset
size = min(offset+1, height)
else:
start = (offset-width+2)*width-1
size = min(height-offset+width-1, width)
step = width - 1
stop = start + size*step
return slice(start, stop, step)
Get and flip a diagonal with slicing:
def flip_antidiagonals(arr, inplace=False):
if not inplace:
arr = arr.copy()
for offset in range(sum(arr.shape)-1):
diag = antidiagonal_slice(offset, *arr.shape)
arr.flat[diag] = arr.flat[diag][::-1]
return arr
Both functions combined together:
import numpy as np
from numpy import njit
@njit
def flip_antidiagonals(arr, inplace=False):
if not inplace:
arr = arr.copy()
height, width = shape = arr.shape
if height == 1 or width == 1:
return arr
arr = arr.reshape(-1)
step = width - 1
for offset in range(height+width-1):
if offset < width:
start = offset
size = min(offset+1, height)
else:
start = (offset-width+2)*width-1
size = min(height-offset+width-1, width)
stop = start + size*step
diag = slice(start, stop, step)
arr[diag] = arr[diag][::-1]
return arr.reshape(shape)
>>> arr = np.array([[1, 2, 4], [3, 5, 7], [6, 8, 10], [9, 11, 13], [12, 14, 15]])
>>> print('Array:', arr, '', 'Flipped diagonals:', flip_antidiagonals(arr), sep='\n')
Array:
[[ 1 2 4]
[ 3 5 7]
[ 6 8 10]
[ 9 11 13]
[12 14 15]]
Flipped diagonals:
[[ 1 3 6]
[ 2 5 9]
[ 4 8 12]
[ 7 11 14]
[10 13 15]]
Upvotes: 1
Reputation: 7260
Vector abstraction
Let's consider the coordinates of cells as vectors on the vector plane (see the picture below). In this case, we can find the target point as follows:
def mirror(pi, pj, m, n) -> list:
'''Returns the point on the reverse transposed diagonal.
(pi, pj) - source point, (m, n) - maximum axis coordinates'''
P = np.array([pi, pj])
p_sum = P.sum()
A = np.array([min(p_sum, m), max(p_sum - m, 0)])
B = np.array([max(p_sum - n, 0), min(p_sum, n)])
M = A + B - P
return M.tolist()
In this figure:
- P is a source point
- M is a target point
- A and B are the extreme points of the diagonal with P
In vectorized form, the formula might look like this:
def transpose_reversed_diag(arr):
m, n = arr.shape
P = np.array(np.meshgrid(np.arange(m), np.arange(n), indexing='ij'))
m -= 1
n -= 1
psum = P.sum(0)
A = np.where(
psum < m,
np.stack([psum, np.zeros_like(psum)]),
np.stack([np.full_like(psum, m), psum - m]),
)
B = np.where(
psum < n,
np.stack([np.zeros_like(psum), psum]),
np.stack([psum - n, np.full_like(psum, n)])
)
return arr[*(A + B - P)]
Diagonal as part of a square
Suppose we know the top left corner and the length of a square. In this case, we can transpose the opposite diagonal in the square this way:
import numpy as np
from numba import njit
@njit
def _flip_diag(ai, aj, length, arr):
'''Transpose the diagonal of a square
with the top left corner (ai, aj) and the given length
which is placed in the 2d-array arr'''
i, j = 0, length
while i < j:
left = ai+i, aj+j
right = ai+j, aj+i
arr[left], arr[right] = arr[right], arr[left]
i += 1
j -= 1
So we can solve the initial task by iterating over the squares build on each diagonal of the array:
@njit
def transpose(arr, inplace=False):
out = arr if inplace else arr.copy()
m, n = arr.shape
if m == n:
return out.T
if m < n:
return transpose(out.T, inplace=True).T
for d in range(n-1): # upper left triangle
_flip_diag(0, 0, d, out)
for d in range(m-n+1): # main body
_flip_diag(d, 0, n-1, out)
for d in range(1, n): # lower right triangle
_flip_diag(m-n+d, d, n-1-d, out)
return out
Flipping diagonals in place
For arrays with a simple and well organized structure (no stride tricks, no complex transpositions, no other weirdness in the data structure under the hood) we can try to force returned diagonals be writeable:
arr = np.array([
[ 1, 2, 4],
[ 3, 5, 7],
[ 6, 8, 10],
[ 9, 11, 13],
[12, 14, 16],
[15, 17, 18],
])
print('Data before mirroring:', arr, '', sep='\n')
height, width = arr.shape
fliplr_arr = np.fliplr(arr)
for offset in range(-(height-1), width):
diag = fliplr_arr.diagonal(offset)
diag.flags.writeable = True # USE WITH CAUTION
diag[:] = diag[::-1]
print('Data after mirroring:', arr, sep='\n')
Data before mirroring:
[[ 1 2 4]
[ 3 5 7]
[ 6 8 10]
[ 9 11 13]
[12 14 16]
[15 17 18]]
Data after mirroring:
[[ 1 3 6]
[ 2 5 9]
[ 4 8 12]
[ 7 11 15]
[10 14 17]
[13 16 18]]
Upvotes: 3
Reputation:
Below code helpful in understanding the NumPy internals in the context of the question, along with the timings of different algorithms applied to array of same size ( see the answer https://stackoverflow.com/a/78599615/7711283 by no comment for code ), but with different shapes, showing that even the 1D-approach, in spite of being always at the same position in the ranking shows different timing depending on array shape:
#!/usr/bin/python
import numpy as np
''' Arrays in numpy are stored in contiguous blocks of memory and the access to array
values requires calculation of a memory offset to array base address done
using the values of indices and the values from the strides tuple
which will be updated on changes of array shape tuple. '''
## Creating a transposed array view on array setting values for shape and strides:
from numpy.lib.stride_tricks import as_strided as getViewSettingValuesForShapeAndStridesOfArray
arr = np.array( [ [1, 2, 3], [4, 5, 6] ]); print(arr)
arrTview = getViewSettingValuesForShapeAndStridesOfArray( arr, arr.shape[::-1], arr.strides[::-1])
print(arrTview)
print(f'{"Array Shape:":27s} {arr.shape = }')
print(f'{"Dimensions:":27s} {arr.ndim = }'); assert arr.ndim == len(arr.shape)
print(f'{"Row,Column Indices Factors:":27s} {arr.strides = }')
print(f'{"Data Type:":27s} {arr.dtype = }')
print(f'{"DataPointer:":27s} {arr.data = }')
print(f'{"Transposed Data Pointer:":27s} {arr.T.data = }') ; assert str(arr.T.data) == str(arr.data)
print(f'{"Array Size (elements):":27s} {arr.size = }')
print(f'{"Array Element Size:":27s} {arr.itemsize = }')
print(f'{"Array Size (bytes):":27s} {arr.nbytes = }')
print(f'{"Flags:":27s} arr.flags = ... \n{arr.flags}')
''' C -> C programming language default row/column order in memory
F -> Fortran programming default row/column order in memory '''
print(f'{"Flags Transposed VIEW:":27s} arr.T.flags = ... \n{arr.T.flags}')
print(f'{"Flags strideTransp. VIEW:":27s} arrTview.flags = ... \n{arrTview.flags}', end="")
Output:
[[1 2 3]
[4 5 6]]
[[1 4]
[2 5]
[3 6]]
Array Shape: arr.shape = (2, 3)
Dimensions: arr.ndim = 2
Row,Column Indices Factors: arr.strides = (24, 8)
Data Type: arr.dtype = dtype('int64')
DataPointer: arr.data = <memory at 0x7f66e01bf9f0>
Transposed Data Pointer: arr.T.data = <memory at 0x7f66e01bf9f0>
Array Size (elements): arr.size = 6
Array Element Size: arr.itemsize = 8
Array Size (bytes): arr.nbytes = 48
Flags: arr.flags = ...
C_CONTIGUOUS : True
F_CONTIGUOUS : False
OWNDATA : True
WRITEABLE : True
ALIGNED : True
WRITEBACKIFCOPY : False
Flags Transposed VIEW: arr.T.flags = ...
C_CONTIGUOUS : False
F_CONTIGUOUS : True
OWNDATA : False
WRITEABLE : True
ALIGNED : True
WRITEBACKIFCOPY : False
Flags strideTransp. VIEW: arrTview.flags = ...
C_CONTIGUOUS : False
F_CONTIGUOUS : True
OWNDATA : False
WRITEABLE : True
ALIGNED : True
WRITEBACKIFCOPY : False
Python: 3.10.12 (main, Nov 20 2023, 15:14:05) [GCC 11.4.0]
ArrayShape: m=108 n=19200
3.7 ± 0.0 ms mirror_prepared_1d
5.0 ± 0.1 ms mirror_shearing
10.9 ± 0.1 ms mirror_prepared
58.8 ± 0.4 ms mirror
------------------
ArrayShape: m=10800 n=192
5.0 ± 0.1 ms mirror_prepared_1d
12.8 ± 0.1 ms mirror_prepared
60.8 ± 0.1 ms mirror
73.9 ± 0.2 ms mirror_shearing
------------------
ArrayShape: m=1080 n=1920
6.0 ± 0.1 ms mirror_prepared_1d
10.6 ± 1.1 ms mirror_shearing
14.7 ± 0.1 ms mirror_prepared
62.1 ± 0.3 ms mirror
Upvotes: 0
Reputation: 10474
Here's a fast solution for when you apply the transformation to many arrays of the same size. Times for your 1080×1920 test case:
4.9 ± 0.1 ms mirror_prepared_1d
6.6 ± 0.2 ms mirror_shearing
15.7 ± 0.1 ms mirror_prepared
60.8 ± 0.4 ms mirror
Python: 3.12.2 (main, May 17 2024, 19:27:45) [GCC 14.1.1 20240507]
The mirror solution is from my first answer. When given an array, it computes the transformation indices and applies them.
In the comments you mentioned "if the same view is needed for many arrays creating a mapping once will benefit all the subsequent uses", so mirror_prepared does that. It prepares the transformation indices beforehand and when given an array, it only applies them.
You also commented about "leave the perspective of an actual existence of an 2D array", so mirror_prepared_1d does that. It computes 1D transformation indices beforehand and when given an array (in 2D), it creates a 1D view, applies the 1D transformation, and reshapes to 2D.
The mirror_shearing solution is my second answer's totally different approach.
import numpy as np
from timeit import timeit
from statistics import mean, stdev
import sys
import random
m, n = 1080, 1920
a = np.arange(1, m*n+1, dtype=np.uint32).reshape((m, n))
# The index transformation function
def ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt(i,j,arrShapeRows,arrShapeColumns):
d = i + j
o = np.fmin(d, arrShapeRows-1) - np.fmin(d, arrShapeColumns-1)
return j+o, i-o
# Applying the function to the whole array
def mirror(a):
ijFunc = ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt
return a[ijFunc(*np.indices(a.shape), *a.shape)]
# Version that uses lookup indices prepared in advance
def mirror_prepared(a):
return a[prepared_ij]
ijFunc = ijIndicesToSourceArray_gettingValueOfSourceArrayWithReversedRightLeftAntiDiagonalsAt
prepared_ij = ijFunc(*np.indices(a.shape), *a.shape)
# Version that uses 1D lookup indices prepared in advance
def mirror_prepared_1d(a):
return a.ravel()[prepared_ij_1d].reshape(a.shape)
prepared_ij_1d = prepared_ij[0] * n + prepared_ij[1]
def mirror_shearing(a):
m, n = a.shape
if m == n:
return a.T.copy()
if m > n:
return mirror(a.T).T
# Shear
v = a.flatten()
w = v[:-m].reshape((m, n-1))
# Flip the parallelogram
w[:, m-1:] = w[::-1, m-1:]
# Flip the triangles
t = np.vstack((w[:, :m-1].reshape((m-1, m)), v[-m:]))
t = t.T
w[:, :m-1] = t[:-1].reshape((m, m-1))
# Write flipped parts back and unshear
v[:-m] = w.ravel()
v[-m:] = t[-1]
return v.reshape((m, n))
funcs = [mirror, mirror_prepared, mirror_prepared_1d, mirror_shearing]
# Correctness
original = a.copy()
expect = mirror(a)
for f in funcs:
assert np.array_equal(f(a), expect), f
assert np.array_equal(a, original), f
# Speed
times = {f: [] for f in funcs}
def stats(f):
ts = [t * 1e3 for t in sorted(times[f])[:5]]
return f'{mean(ts):5.1f} ± {stdev(ts):3.1f} ms '
for _ in range(25):
random.shuffle(funcs)
for f in funcs:
t = timeit(lambda: f(a), number=1)
times[f].append(t)
for f in sorted(funcs, key=stats):
print(stats(f), f.__name__)
print('\nPython:', sys.version)
Upvotes: 1
Reputation: 102625
Python Implementation
With numpy, you can use outer + reshape like below
import numpy as np
def flip_along_diagonal(m):
d1= range(m.shape[0])
d2 = range(m.shape[1])
grp = np.add.outer(d1,d2).flatten("F")
x = m.flatten("F")
for k in np.unique(grp):
msk = grp==k
x[msk] = x[msk][::-1]
return np.reshape(x, m.shape,"F")
Output
With input data
m = np.array(
[
[1, 2, 3, 4, 5, 6],
[7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24],
]
)
you will obtain
# flip_along_diagonal(m)
array([[ 1, 7, 13, 19, 20, 21],
[ 2, 8, 14, 15, 16, 22],
[ 3, 9, 10, 11, 17, 23],
[ 4, 5, 6, 12, 18, 24]])
and
# flip_along_diagonal(flip_along_diagonal(m))
array([[ 1, 2, 3, 4, 5, 6],
[ 7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24]])
R equivalence
If you are interested in R implementations, here is one option with the same design philosophy as in python, but would be much shorter
flip_along_diagonal <- function(m) {
grp <- col(m) + row(m)
`dim<-`(ave(m, grp, FUN = rev), dim(m))
}
and some output examples
> (m1 <- matrix(1:12, 3))
[,1] [,2] [,3] [,4]
[1,] 1 4 7 10
[2,] 2 5 8 11
[3,] 3 6 9 12
> flip_along_diagonal(m1)
[,1] [,2] [,3] [,4]
[1,] 1 2 3 6
[2,] 4 5 8 9
[3,] 7 10 11 12
> (m2 <- matrix(1:10, 5))
[,1] [,2]
[1,] 1 6
[2,] 2 7
[3,] 3 8
[4,] 4 9
[5,] 5 10
> flip_along_diagonal(m2)
[,1] [,2]
[1,] 1 2
[2,] 6 3
[3,] 7 4
[4,] 8 5
[5,] 9 10
> (m3 <- matrix(1:25, 5))
[,1] [,2] [,3] [,4] [,5]
[1,] 1 6 11 16 21
[2,] 2 7 12 17 22
[3,] 3 8 13 18 23
[4,] 4 9 14 19 24
[5,] 5 10 15 20 25
> flip_along_diagonal(m3)
[,1] [,2] [,3] [,4] [,5]
[1,] 1 2 3 4 5
[2,] 6 7 8 9 10
[3,] 11 12 13 14 15
[4,] 16 17 18 19 20
[5,] 21 22 23 24 25
Timing R vs Python Solutions
running over a 1080-by-1920 matrix:
RTiming Example
set.seed(0)
nr <- 1080
nc <- 1920
m <- matrix(rnorm(nr * nc), nr)
shows 0.29s
> system.time(flip_along_diagonal(m))
user system elapsed
0.17 0.12 0.29
PythonTiming Example
nc, nr = 1080, 1920
m = np.random.randint(0, 10, (nc, nr))
start = time.time()
flip_along_diagonal(m)
time.time() - start
shows 6.7s
6.7068586349487305
Upvotes: 0
Reputation: 10474
This one seems fairly fast, especially for wide matrices like your width=n=1920, height=m=1080 :
def mirror(a):
m, n = a.shape
if m == n:
return a.T.copy()
if m > n:
return mirror(a.T).T
# Shear
v = a.flatten()
w = v[:-m].reshape((m, n-1))
# Flip the parallelogram
w[:, m-1:] = w[::-1, m-1:]
# Flip the triangles
t = np.vstack((w[:, :m-1].reshape((m-1, m)), v[-m:]))
t = t.T
w[:, :m-1] = t[:-1].reshape((m, m-1))
# Write flipped parts back and unshear
v[:-m] = w.ravel()
v[-m:] = t[-1]
return v.reshape((m, n))
The idea: Slice/reshape the m×n matrix to an m×(n-1) matrix so that the parallelogram (green part) becomes a rectangle so we can just flip it upside down. For example:
Now reshape the m×n matrix to an m×(n-1) matrix (omit the black last m cells), which moves the yellow cells to the front of the next row, shifting the next row as needed:
Now we can easily flip the green parallelogram part. For the top-left and bottom-right triangles, reshape/shear the left part of this back and put the omitted cells under it:
This can now simply be transposed and written back.
Upvotes: 2
Reputation: 1886
I believe this is similar to one of the other answers, but easier to follow (to me, anyway). Basically, we transpose the upper and lower triangles and flip the remaining diagonals. Because Numpy has several functions to deal with main diagonals, start by flipping the array along axis 1.
def flip_anti_diags(x: np.ndarray) -> np.ndarray:
if x.shape[0] == x.shape[1]:
return x.T
# Handle wide matrices
transpose = x.shape[0] < x.shape[1]
if transpose:
x = x.T
# Smallest dimension
s = x.shape[1]
# Numpy has various functions to obtain main diagonals and triangles,
# so flip x so these work
x = np.fliplr(x)
# Get the upper and lower triangles, without any other diagonals,
# but don't transpose them yet as we need them for the diagonals
u = np.triu(x)
l = np.tril(x, x.shape[1] - x.shape[0])
# Get the diagonals and flip them, returning the flipped anti-diagonals
m = x - u - l
m = np.fliplr(m)
m = m.T.ravel()[: -x.shape[1]]
m = m.reshape((x.shape[1], x.shape[0] - 1))
m = np.flipud(m)
m = np.pad(m.ravel(), (0, x.shape[1]))
m = m.reshape(x.shape[::-1]).T
# Get the transposed upper and lower triangles
u = np.fliplr(u)
u = u[:s].T
l = np.fliplr(l)
l = l[-s:].T
# Combine the diagonals and the transposed triangles
x = m
x[:s] += u
x[-s:] += l
# Flip back, if necessary
if transpose:
x = x.T
return x
Upvotes: 1
Reputation: 50949
You can create a list of all the diagonals and reassigned them back to the array by vectors
def flip_diagonals(arr):
rows, cols = arr.shape
arr = np.fliplr(arr)
diagonals = [arr.diagonal(offset=i).copy() for i in range(cols - 1, -rows, -1)]
inc_rows = 0
inc_cols = 0
for i, diag in enumerate(diagonals, start=1):
diag_len = len(diag)
if i > rows:
rows_diag = np.arange(rows)[-diag_len:]
if min(rows, cols) > diag_len:
cols_diag = np.arange(cols)[-diag_len:]
else:
inc_cols += 1
cols_diag = np.arange(cols)[:diag_len] + inc_cols
arr[rows_diag[::-1], cols_diag] = diag
else:
new_diag = np.arange(diag_len)
arr[new_diag[::-1] + inc_rows, new_diag] = diag
inc_rows = inc_rows + 1 if diag_len == cols else 0
return arr
arr1 = np.array([[1, 2, 4],
[3, 5, 7],
[6, 8, 10],
[9, 11, 13],
[12, 14, 15]])
arr2 = np.array([[ 1, 2, 3, 4, 5, 6],
[ 7, 8, 9, 10, 11, 12],
[13, 14, 15, 16, 17, 18],
[19, 20, 21, 22, 23, 24]])
arr1 = flip_diagonals(arr1)
print(arr1)
arr2 = flip_diagonals(arr2)
print(arr2)
Output:
[[ 1 3 6]
[ 2 5 9]
[ 4 8 12]
[ 7 11 14]
[10 13 15]]
[[ 1 7 13 19 20 21]
[ 2 8 14 15 16 22]
[ 3 9 10 11 17 23]
[ 4 5 6 12 18 24]]
Upvotes: 0
Reputation: 9086
I don't think there is any efficient way to do this. I would just do it similar to how I said to create the array from its diagonals in this answer, but reversing the diagonals along the way.
import numpy as np
from scipy.sparse import diags
a = np.arange(15).reshape(5,3) + 1
n, m = a.shape
print(a)
offsets = np.arange(n+m-1)[::-1]-(a.shape[0]-1)
aflipped = np.fliplr(a)
diagonals = [np.diagonal(aflipped, offset=i) for i in offsets]
b = np.zeros_like(a)
for diagonal, offset in zip(diagonals, offsets):
b += diags(diagonal[::-1], offset, shape=a.shape).astype(int)
b = np.fliplr(b)
print(b)
Upvotes: 0
Reputation:
For the sake of completeness and for the sake of having an accepted answer below both the by me written fastest approach among all other in the other answers provided ones ( status 2024-06-03 ) and as reference an approach allowing getting single values out of the source array without the need of creating a target one just by calculating appropriate indices and therefore very fast for this purpose (based on code provided in the bountied answer by Johnny Cheesecutter).
The fastest approach provided below is using Python loops and numpy slices and for to me unknown reason actually slows down if "accelerated" by numba :
import numpy as np
from time import perf_counter as T
import numba as nb
#""" # <- "Magic Switch" : add/remove leading `#` to switch between two blocks of code
testShapes=[ (5,3), (3,5), (4,8), (8,4), (4,5), (5,4), (4,4), (5,5) ]
"""
testShapes=[ (4,7) ]
#"""
@nb.njit(cache=True,fastmath=True)
def flipOverRLdiags(a):
''' Can easily be adapted to provide `new_i, new_j` given i , j and mRows, nCols
and is the fastest numba based approach used here as reference . Constructed
using in the bountied answer by Johnny Cheesecutter provided code for
obtaining the target indices and faster than in this answer itself provided
code for obtaining the resulting array: '''
mRows, nCols = a.shape
t = min(mRows, nCols)
b = a.copy() # faster than np.empty_like(a) -> how does it come ?
for i in range(mRows):
for j in range(nCols):
# top/left "triangle"
if i < t and i + j < t :
new_i , new_j = j , i
b[i , j] = a[ new_i , new_j ]
continue
# bottom/right "triangle"
if (mRows-1-i) < t and (mRows-1-i) + (nCols-1-j) < t:
new_i , new_j = (mRows-1-i) , (nCols-1-j)
new_i, new_j = mRows - 1 - new_j , nCols - 1 - new_i
b[i , j] = a[ new_i , new_j ]
continue
# "parallelogram"
if mRows >= nCols:
new_j = nCols - 1 - j
new_i = i - (new_j - j )
b[ i , j ] = a[ new_i , new_j ]
continue
else:
new_i = mRows - 1 - i
new_j = j - (new_i-i)
b[i , j] = a[ new_i , new_j ]
continue
return b
#@nb.njit( cache=True, fastmath=True) # <- for to me unknown reason using numba
# ^-- SLOWS DOWN instead of making faster
def flipRLdiagsOf(arrA) :
''' Python loops plus numpy slices appears to be the overall fastest approach. '''
a = arrA
mRows, nCols = a.shape
absDiffColsRows = abs(nCols-mRows)
if absDiffColsRows == 0 : # we have a square array where transposing is enough so:
b = a.T.copy()
return b ## <- END : because of square array case
b = a.copy() # for to me unknown reason faster than `np.empty_like(a)`
aT = a.T
maxDiagLen = min(mRows, nCols)
for diagLen in range(1 , maxDiagLen + 1) :
b[ maxDiagLen - diagLen , :diagLen] = \
aT[ maxDiagLen - diagLen , :diagLen] # copy flipped upper/left "triangle"
b[ mRows - diagLen , -(maxDiagLen - diagLen) -1 : ] = \
aT[ nCols - diagLen , -(maxDiagLen - diagLen) -1 : ] # copy flipped lower/right "triangle"
if absDiffColsRows <= 1 : # we are ready because all values are already assigned :
return b ## <- END : both "triangles" are flipped
# Now if reached this line flipping the "parallelogram" part of the array:
if mRows > nCols : # we have the case of a "narrow: array (more rows than columns) :
for col in range(nCols):
startRow = (nCols - 1) - col
b[ startRow : startRow + absDiffColsRows , col ] = \
a[ col : col + absDiffColsRows , startRow ] #
if nCols > mRows : # we have the case of a "wide" array (more columns than rows) :
for row in range(mRows):
startCol = (mRows - 1) - row
b[ row , startCol : startCol + absDiffColsRows ] = \
a[ startCol , row : row + absDiffColsRows ] #
return b ## <- END : both "triangles" and the "parallelogram" are flipped
for nCols, mRows in testShapes :
srcArr = np.arange(11, nCols * mRows +11, dtype=np.uint8).reshape((mRows , nCols))
print(srcArr, end="")
print("\n -=-=-=-=-")
tgtArr1 = flipOverRLdiags(srcArr)
tgtArr2 = flipRLdiagsOf(srcArr)
print(tgtArr2, end="")
print("\n============")
assert np.all(tgtArr1 == tgtArr2)
# exit()
# from srcArr import srcArr
srcArr = np.arange(1,1920*1080+1, dtype=np.uint32).reshape((1080, 1920))
sT1=T()
tgtArr1 = flipOverRLdiags(srcArr)
dT1=T()-sT1
sT2=T()
tgtArr2 = flipRLdiagsOf(srcArr)
dT2=T()-sT2
print()
print(dT1, dT2)
assert np.all(tgtArr1 == tgtArr2)
outputs:
[[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]]
-=-=-=-=-
[[11 16 21 22 23]
[12 17 18 19 24]
[13 14 15 20 25]]
============
[[11 12 13]
[14 15 16]
[17 18 19]
[20 21 22]
[23 24 25]]
-=-=-=-=-
[[11 14 17]
[12 15 20]
[13 18 23]
[16 21 24]
[19 22 25]]
============
[[11 12 13 14]
[15 16 17 18]
[19 20 21 22]
[23 24 25 26]
[27 28 29 30]
[31 32 33 34]
[35 36 37 38]
[39 40 41 42]]
-=-=-=-=-
[[11 15 19 23]
[12 16 20 27]
[13 17 24 31]
[14 21 28 35]
[18 25 32 39]
[22 29 36 40]
[26 33 37 41]
[30 34 38 42]]
============
[[11 12 13 14 15 16 17 18]
[19 20 21 22 23 24 25 26]
[27 28 29 30 31 32 33 34]
[35 36 37 38 39 40 41 42]]
-=-=-=-=-
[[11 19 27 35 36 37 38 39]
[12 20 28 29 30 31 32 40]
[13 21 22 23 24 25 33 41]
[14 15 16 17 18 26 34 42]]
============
[[11 12 13 14]
[15 16 17 18]
[19 20 21 22]
[23 24 25 26]
[27 28 29 30]]
-=-=-=-=-
[[11 15 19 23]
[12 16 20 27]
[13 17 24 28]
[14 21 25 29]
[18 22 26 30]]
============
[[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
[26 27 28 29 30]]
-=-=-=-=-
[[11 16 21 26 27]
[12 17 22 23 28]
[13 18 19 24 29]
[14 15 20 25 30]]
============
[[11 12 13 14]
[15 16 17 18]
[19 20 21 22]
[23 24 25 26]]
-=-=-=-=-
[[11 15 19 23]
[12 16 20 24]
[13 17 21 25]
[14 18 22 26]]
============
[[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]
[26 27 28 29 30]
[31 32 33 34 35]]
-=-=-=-=-
[[11 16 21 26 31]
[12 17 22 27 32]
[13 18 23 28 33]
[14 19 24 29 34]
[15 20 25 30 35]]
============
0.01775594600258046 0.013043331997323548
The core idea of the Python loops and numpy slices using approach, which turned out to be the most effective, is creating in first step a view into transposed source array to copy the flipped top and bottom "triangles" from it to the resulting array. The second and final step is "mirroring" column by column (or row by row, depending on array shape) the vertical (or horizontal) slices within the "parallelogram" part of the source array copying them over from the source into the target array.
Here again the line with timing of flipping an np.uint32 1080x1920 array over the right-left(anti-)diagonals:
0.01775594600258046 0.013043331997323548
The first time is the time of the reference code and the second result the time of the up to now fastest approach ( status 2024-06-03 ).
Upvotes: 1
Reputation: 4181
A simple way to break down this problem, without using any loops:
- Step 1: Transpose the upper and lower triangles (red and blue)
- Step 2: Flip the "parallelogram" in the middle (purple)
When the matrix is square (h=w), just transpose is enough. I'm showing an example when the matrix is "tall" (h > w):
def flip_along_diag(a):
h, w = a.shape
out = np.zeros_like(a)
# step 1: flip upper and lower triangles
u, v = np.triu_indices(w, 0)
p, q = np.tril_indices(w, 0)
out[u, w-v-1] = a[w-v-1, u]
out[h-w+p, w-1-q] = a[h-1-q, p]
# step 2: flip the "parallelogram" of size (r, s) in the middle
r, s = h - w - 1, w
if r >= 1:
i, j = np.mgrid[:r, :s]
i = i + np.arange(s)[::-1] + 1
out[i, j] = np.fliplr(a[i, j])
return out
I believe the same algorithm can be extended when the matrix is wide (w > h) instead of tall, with a little modification.
Update: For handling the case of wide (w > h) matrices, we can simply first check if w > h, and then simply modify the indices as needed.
def flip_along_diag(a):
h, w = a.shape
if h == w: # for square matrix, a.T is enough
return a.T
out = np.zeros_like(a)
k, d = min(h, w), abs(h - w)
# step 1: flip two triangles
u, v = np.triu_indices(k, 0)
p, q = np.tril_indices(k, 0)
if h > w: # h > w: upper and lower triangle
out[u, k-v-1] = a[k-v-1, u]
out[d+p, w-q-1] = a[h-q-1, p]
else: # w > h: left and right triangle
out[u, k-v-1] = a[k-v-1, u]
out[p, w-q-1] = a[h-q-1, d+p]
# step 2: flip parallelogram
if h > w: # h > w: flip left-right
r, s = h - w - 1, w
if r >= 1:
i, j = np.mgrid[:r, :s]
i = i + np.arange(s)[::-1] + 1
out[i, j] = np.fliplr(a[i, j])
else: # w > h: flip up-down
r, s = h, w - h - 1
if s >= 1:
i, j = np.mgrid[:r, :s]
j = j + np.arange(r)[::-1, None] + 1
out[i, j] = np.flipud(a[i, j])
return out
Upvotes: 9
Reputation: 2852
I would propose approach similar to the one proposed by previous contributor, but with fast for loops in numba.
Step by step:
First let's mirror upper left triangle and bottom right triangle
Switch elements in the parallelogram between this two triangles:
- such parallelogram could either be vertical
- or it could be horizontal
import numpy as np
import numba as nb
from timeit import timeit
@nb.njit(cache=True,fastmath=True)
def mirror(a):
n_rows, n_cols = a.shape[:2]
b = a.copy()
t = min(n_rows, n_cols)
# mirror upper left and bottom right triangles
for i in range(1, t-1):
for j in range(min(i, t-1-i)):
# inverting upper left triangle
b[i,j], b[j,i] = a[j,i], a[i,j]
# inverting bottom right triangle
b[n_rows-1-i,n_cols-1-j], b[n_rows-1-j,n_cols-1-i] = a[n_rows-1-j,n_cols-1-i], a[n_rows-1-i,n_cols-1-j]
# mirror middle parallelogram
if n_rows>=n_cols:
for i in range(int(t/2)):
b[t-1-i:n_rows-i,i], b[i:n_rows-t+1+i, n_cols-1-i] = a[i:n_rows-t+1+i, n_cols-1-i], a[t-1-i:n_rows-i,i]
else:
for i in range(int(t/2)):
b[i, t-1-i:n_cols-i ], b[n_rows-1-i, i:n_cols-t+1+i ] = a[n_rows-1-i, i:n_cols-t+1+i ], a[i, t-1-i:n_cols-i ]
return b
def generate_random_matrx(n_rows: int, n_cols: int):
return np.arange(1,1+n_rows*n_cols).reshape(n_rows, n_cols)
def test1():
A = [[ 1, 2, 3, 4, 5],
[ 6, 7, 8, 9, 10],
[11, 12, 13, 14, 15],
[16, 17, 18, 19, 20],
[21, 22, 23, 24, 25]]
A = np.array(A)
B = mirror(A)
A_out = [[ 1, 6, 11, 16, 21],
[ 2, 7, 12, 17, 22],
[ 3, 8, 13, 18, 23],
[ 4, 9, 14, 19, 24],
[ 5, 10, 15, 20, 25]]
A_out = np.array(A_out)
assert np.all(B == A_out)
def test2():
A = [[ 1, 2, 3],
[ 4, 5, 6],
[ 7, 8, 9],
[10, 11, 12],
[13, 14, 15],
[16, 17, 18],
[19, 20, 21],
[22, 23, 24],
[25, 26, 27],
[28, 29, 30]]
A = np.array(A)
B = mirror(A)
A_out = [[ 1, 4, 7],
[ 2, 5, 10],
[ 3, 8, 13],
[ 6, 11, 16],
[ 9, 14, 19],
[12, 17, 22],
[15, 20, 25],
[18, 23, 28],
[21, 26, 29],
[24, 27, 30]]
A_out = np.array(A_out)
assert np.all(B == A_out)
def test3():
A = [[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
[11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
[21, 22, 23, 24, 25, 26, 27, 28, 29, 30],
[31, 32, 33, 34, 35, 36, 37, 38, 39, 40]]
A = np.array(A)
B = mirror(A)
A_out = [[ 1, 11, 21, 31, 32, 33, 34, 35, 36, 37],
[ 2, 12, 22, 23, 24, 25, 26, 27, 28, 38],
[ 3, 13, 14, 15, 16, 17, 18, 19, 29, 39],
[ 4, 5, 6, 7, 8, 9, 10, 20, 30, 40]]
A_out = np.array(A_out)
assert np.all(B == A_out)
A = generate_random_matrx(3, 10)
print(A)
B = mirror(A)
print(B)
test1()
test2()
test3()
Function that takes indices as inputs:
@nb.njit(cache=True,fastmath=True)
def get_indices(i:int,j:int,n_rows:int,n_cols:int):
t = min(n_rows, n_cols)
# upper left triangle
if i<t and i+j<t:
return (j,i)
# bottom right triangle
if (n_rows-1-i)<t and (n_rows-1-i) + (n_cols-1-j)<t:
i, j = (n_rows-1-i), (n_cols-1-j)
return (n_rows-1-j,n_cols-1-i)
# parallelograms
if n_rows>=n_cols:
new_j = n_cols-1-j
return (i- (new_j-j), new_j)
else:
new_i = n_rows-1-i
return (new_i, j - (new_i-i))
Upvotes: 3
Reputation: 1419
The sum of indices on anti-diagonals preserves. This means you can construct array with indices sum, like this (given a is your array):
rows, cols = np.indices(a.shape)
indices_sum = rows + cols
array([[0, 1, 2],
[1, 2, 3],
[2, 3, 4],
[3, 4, 5],
[4, 5, 6]])
and iterate per each unique value, get indices and flip like this:
import numpy as np
rows, cols = np.indices(a.shape)
indices_sum = rows + cols
for i in np.unique(indices_sum):
r, c = np.where(indices_sum==i)
a[r, c] = a[r[::-1], c[::-1]]
Note: you can use np.arange(1, a.shape[0] + a.shape[1] - 2) instead of np.unique(indices_sum)
Here I'm still using python loop, but I think this is simpler solution. You may try to adapt it to exclude the loop.
Upvotes: 1
Reputation: 372
I also have not found a Numpy method to do this.
However, the indices can be generated using this function:
import numpy as np
def flip_inds(a):
m, n = a.shape
i = np.arange(m).reshape(-1, 1)
j = np.arange(n).reshape(1, -1)
jp = np.where(
i + j < min(m, n),
i,
np.where(
i + j < max(m, n),
(
i + j - (m - 1 - i)
if n > m else
n - 1 - j
),
n - (m - i)
)
)
ip = i + j - jp
return ip, jp
ip, jp = flip_inds(a)
a[ip, jp] # diagonals flipped
but I would recommend Numba for this because it will be more efficient:
import numba as nb
@nb.njit
def flip(a):
m, n = a.shape
b = np.empty_like(a)
for i in range(m):
for j in range(n):
# Along a diagonal i + j is constant
# denote by (ip, jp) the indices of the value in the input that should be put in the (i, j) entry of the output
# We know that: i + j = ip + jp
jp = (
# Case 1: (i, j) in upper left triangle
# Here we just do the regular transpose
i
if i + j < min(m, n) else (
# Case 2: (i, j) neither in upper left or lower right triangle
# in this case what we do depends on if n > m or not
# If n > m we are bounded by m, locate ip at i steps from the maximum i index:
# ip = m - 1 - i
# from that we can obtain jp as i + j - ip:
i + j - (m - 1 - i)
if n > m else
# If m > n locate the jp index j steps from the max j index
n - 1 - j
)
if i + j < max(m, n) else
# Case 3: Lower right corner, here we can do a transpose again, but with indices going backwards
n - (m - i)
)
ip = i + j - jp
b[i, j] = a[ip, jp]
return b
flip(a) # diagonals flipped
Without comments (easier to copy):
@nb.njit
def flip(a):
m, n = a.shape
b = np.empty_like(a)
for i in range(m):
for j in range(n):
jp = (
i
if i + j < min(m, n) else (
i + j - (m - 1 - i)
if n > m else
n - 1 - j
)
if i + j < max(m, n) else
n - (m - i)
)
ip = i + j - jp
b[i, j] = a[ip, jp]
return b
Upvotes: 5
Reputation:
As long as there is no better answer demonstrating how to refrain from using Python loops, below an approach which uses only numpy and supports arrays with any type of values (also mixed):
#!/usr/bin/python
import numpy as np
## Decide the shape of the test array :
M =3 ; N=5 # ( M-Rows x N-Columns )
## Create a test array :
srcArr = np.arange( 11, 10+N*M+1,
dtype=np.uint8).reshape(M,N) ; print( srcArr ); print( " ---===--- " )
# ---===---===---===---===---===---===---===---===---===---===---===---===---===---===---===---
## Extend the array to the right with M-1 columns for later "shear" :
tmpArr=np.zeros((M,M-1), dtype=np.uint8) ;# print(tmpArr );print( " ---===--- " )
extArr=np.concatenate( ( srcArr, tmpArr ), axis=1 ) ; print( extArr ); print( " ---===--- " )
## Share the extended array using np.roll() :
for index in range( 1, M):
extArr[index]=np.roll(extArr[index], index)
pass; print( extArr ); print( " ---===--- " )
## And reverse by up/down flipping the order of the former diagonals being now columns :
flpArr = np.flipud(extArr) ; print( flpArr ); print( " ---===--- " )
## Diagonals are reversed and will be "rolled" into their former positions in the array :
for index in range( 0, M +N - 1):
if True : ## The "tricky" part because handling non-square arrays requires handling
flpArr[:,index]=np.roll( flpArr[:,index], ## of three algorithmic different phases
( index + 1 ) if index < min(N,M) ## < Phase A : left, "growing" part of array
else ( -1 * (M + abs(N-M) ) + 2* (index + 1 - min(N,M)) ) ## Phase B :
* ( 1 if ( M - min(N,M) ) and (N+M-1 - 2*N - 1) ## < same "size":
else 0 ) if index < (N+M) - min(N,M) - 1
else -(M+N ) + index + 1 ) ## < Phase C : right, "shinking"
pass; print(flpArr) ; print( " ---===--- " )
for index in range( 1, M): ## Rolling the array back to its initial shape :
flpArr[index]=np.roll( flpArr[index], -index)
pass; print( flpArr) ; print( " ---===--- " )
tgtArr = flpArr[ :M, :N] ## < cut the final array out of the extended one
pass; print(tgtArr) ; print( " ---===--- " )
"""
[[ 1 2 3]
[ 4 5 6]
[ 7 8 9]
[ 10 11 12]
[13 14 15]]
[[ 1 2 3]
[ 4 5 6]
[ 7 8 9]
[10 11 12]
[13 14 15]]
[[ 1 2 3]
[ 4 5 6]
[ 7 8 9]
[10 11 12]
[13 14 15]]
"""
The code outputs :
[[11 12 13 14 15]
[16 17 18 19 20]
[21 22 23 24 25]]
---===---
[[11 12 13 14 15 0 0]
[16 17 18 19 20 0 0]
[21 22 23 24 25 0 0]]
---===---
[[11 12 13 14 15 0 0]
[ 0 16 17 18 19 20 0]
[ 0 0 21 22 23 24 25]]
---===---
[[ 0 0 21 22 23 24 25]
[ 0 16 17 18 19 20 0]
[11 12 13 14 15 0 0]]
---===---
[[11 16 21 22 23 0 0]
[ 0 12 17 18 19 24 0]
[ 0 0 13 14 15 20 25]]
---===---
[[11 16 21 22 23 0 0]
[12 17 18 19 24 0 0]
[13 14 15 20 25 0 0]]
---===---
[[11 16 21 22 23]
[12 17 18 19 24]
[13 14 15 20 25]]
---===---
The above output demonstrates the approach which uses numpy np.roll() making it possible to "shear" the array in order to get the diagonals available for flipping in first place and then unrolling it back to the original shape.
Upvotes: 1
Related Questions
- How to put a Python numpy array back together from diagonals obtained from splitting the array into right to left diagonals in first place?
- Most efficient way to reverse a numpy array
- Numpy: Get indices of boundaries in an array where starts of boundaries always start with a particular number; non-boundaries by a particular number
- ValueError: logits and labels must have the same shape ((None, 2) vs (None, 1))
- How to get a 2D NumPy array with value 1 at indices represented by values in 1D NumPy array (Python)
- Detect if a NumPy array contains at least one non-numeric value?
- Argmax of numpy array returning non-flat indices
- Select based on neighbouring elements
- How do numpy functions operate on pandas objects internally?
- Is there a way to flatten a numpy array in diagonal order efficiently?