How to select pairs of values in an array according to a given sequence for all matrix shapes?

Question

We try to select values from matrices into pairs according to the procedure where values are selected diagonally. my code doesn't work as it should

You can see this sequence in the example below. It can be seen that the values are selected sequentially in a cross-form, where it starts in the penultimate line of the first value and joins it from the second value of the last line. It then moves one line up and continues in the same way.

. In the 1st example, the principle is that it takes cross values in the 1st example 21-> 32, then it starts 11-> 22, 11-> 33,22-> 33,12-> 23 and so on for all matrices. The same goes for the second example

code:

import numpy as np

a=np.array([[11,12,13],
            [21,22,23],
            [31,32,33]])


w,h = a.shape
for y0 in range(1,h):
    y = h-y0-1
    for x in range(h-y-1):
        print( a[y+x,x], a[y+x+1,x+1] )

for x in range(1,w-1):
    for y in range(w-x-1):
        print( a[y,x+y], a[y+1,x+y+1] )

my outupt:

required output

However, if I use this matrix, for example, it will throw me an error.

a=np.array([[11,12,13,14,15,16],
            [21,22,23,24,25,26],
            [31,32,33,34,35,36]])

required output

my output

error

  File "C:\Users\Pifkoooo\dp\skuska.py", line 24, in <module>
    print( a[y+x,x], a[y+x+1,x+1] )

IndexError: index 2 is out of bounds for axis 0 with size 2

Can anyone advise me how to solve this problem and generalize it to work on all matrices with different shapes? Or if there is another way to approach this task?

Nevermind. I understood what you're trying to do. It's not what my solution is doing, so hang on a bit. — Mad Physicist, Apr 23 '21 at 23:20
Wait. I don't understand. Your first example is not doing the same thing as the second. I've posted an answer that does what your first example is doing, not the second. — Mad Physicist, Apr 23 '21 at 23:22
my mistake, now i noticed that anni first example doesn't work on square matrices as it should, bpreto I adjusted the question. The principle is that it takes the cross values in the 1st example 21-> 32, then 11-> 22, 11-> 33,22-> 33,12-> 23 starts an order of magnitude higher and so for all matrices — Ľubomír Rusnák, Apr 23 '21 at 23:29
Ok. That totally invalidates my answer. Concept is the same though. I'll post another — Mad Physicist, Apr 23 '21 at 23:49
I'm very sorry, it's been a deep night in my country so I can't concentrate — Ľubomír Rusnák, Apr 23 '21 at 23:58
It's not night yet in mine, but my concentration is no better :) — Mad Physicist, Apr 23 '21 at 23:59
I've posted a totally vectorized solution. Let me know if it works for you. — Mad Physicist, Apr 27 '21 at 00:51

Alex G · Answer 1 · 2021-04-23T23:53:34.147

Probably not the best performance, but it gets the job done if order does not matter. Iterate over all elements and try to access all of its diagonal partners. If the diagonal partner does not exist catch the raised IndexError and continue with the next element.

def print_diagonal_pairs(a):
    rows, cols = a.shape
    for row in range(rows):
        for col in range(cols):
            max_shift_amount = min(rows, cols) - min(row, col)
            for shift_amount in range(1, max_shift_amount+1):
                try:
                    print(a[row, col], a[row+shift_amount, col+shift_amount])
                except IndexError:
                    continue

a = np.array([
    [11,12,13],
    [21,22,23],
    [31,32,33],
])

print_diagonal_pairs(a)

# Output:
11 22
11 33
12 23
21 32
22 33


b = np.array([
    [11,12,13,14,15,16],
    [21,22,23,24,25,26],
    [31,32,33,34,35,36]
])

print_diagonal_pairs(b)

# Output:
11 22
11 33
12 23
12 34
13 24
13 35
14 25
14 36
15 26
21 32
22 33
23 34
24 35
25 36

see another example – Ľubomír Rusnák Apr 23 '21 at 23:02 — Ľubomír Rusnák, Apr 23 '21 at 23:02

Kevin · Answer 2 · 2021-04-23T23:53:56.500

Not a solution, but I think you can use fancy indexing for this task. In the code snippet below i am selecting the indices x = [[0,1], [0,2], [1,2]] along the first axis. These indices will be broadcasted against the indices in y along the first dimension.

from itertools import combinations

a=np.array([[11,12,13,14,15,16],
            [21,22,23,24,25,26],
            [31,32,33,34,35,36]])

x = np.array(list(combinations(range(a.shape[0]), 2)))
y = x + np.arange(a.shape[1]-2)[:,None,None]

a[x,y].reshape(-1,2)

Output:

array([[11, 22],
       [11, 33],
       [22, 33],
       [12, 23],
       [12, 34],
       [23, 34],
       [13, 24],
       [13, 35],
       [24, 35],
       [14, 25],
       [14, 36],
       [25, 36]])

This will select all correct values except for the start and end values for the second example. There is probably a smart way to include these edge values and select all values in one sweep, but I cannot think of a solution for this atm.

I thought the pattern was to select combinations of size 2 along each diagonal, but apparently not - so this solution will not give the correct "middle" values in your first example.

EDIT

You could extend the selection range and modify the two edge values:

x = np.array(list(combinations(range(a.shape[0]), 2)))
y = x + np.arange(-1,a.shape[1]-1)[:,None,None]

# assign edge values
y[0] = y[1][0]
y[-1] = y[-2][-1]
a[x,y].reshape(-1,2)[2:-2]

Output:

array([[21, 32],
       [11, 22],
       [11, 33],
       [22, 33],
       [12, 23],
       [12, 34],
       [23, 34],
       [13, 24],
       [13, 35],
       [24, 35],
       [14, 25],
       [14, 36],
       [25, 36],
       [15, 26]])

it fits, only as the first combination should be 21 32 and then 11 22 — Ľubomír Rusnák, Apr 23 '21 at 23:33
@ĽubomírRusnák I edited my answer. I think this should work but might need some modification to generalize. — Kevin, Apr 23 '21 at 23:56
As an extra you could use ```x = np.transpose(np.triu_indices(a.shape[0],1))``` to get the combinations - which i slightly faster I think and you don't need to import ```itertools```. — Kevin, Apr 24 '21 at 00:11

score 0 · Answer 3 · answered Apr 23 '21 at 23:18

Let's look for patterns (like here, but simpler)! First, let's say that you have an array of shape (M, N), with M=4 and N=5. First, let's note the linear indices of the elements:

i = 
   0  1  2  3  4
   5  6  7  8  9
  10 11 12 13 14
  15 16 17 18 19

Once you have identified the first element in a pair, the linear index of the next element is just i + N + 1.

Now let's try to establish the path of the first element using the example in the linked question. First, look at the column indices and the row indices:

x = 
   0  1  2  3  4
   0  1  2  3  4
   0  1  2  3  4
   0  1  2  3  4
y = 
   0  0  0  0  0
   1  1  1  1  1
   2  2  2  2  2
   3  3  3  3  3

Now take the difference, and add a factor to account for the shape:

x - y + 2M - N =
   3  4  5  6  7
   2  3  4  5  6
   1  2  3  4  5
   0  1  2  3  4

The first element follows the index of the diagonals except at the bottom row and rightmost column. If you can stably argsort this array (np.argsort has a stable method that uses timsort), then apply that index to the linear indices, you have the path taken by the first element of every pair for any matrix at all. The first observation will then yield the second element.

So it all boils down to this:

M, N = a.shape
path = (np.arange(N - 1) - np.arange(M - 1)[:, None] + 2 * M - N).argsort(None)
indices = np.arange(M * N).reshape(M, N)[:-1, :-1].ravel()[path]

Now you have a couple of different options going forward:

Apply linear indices to the raveled a:

result = a.ravel()[indices[:, None] + [0, N + 1]]

Preserve the shape of a and use np.unravel_index to transform indices and indices + N + 1 into a 2D index:
```
result = a[np.unravel_index(indices[:, None] + [0, N + 1], a.shape)]
```

Moral of the story: this is all black magic!

score 0 · Answer 4 · answered Apr 25 '21 at 21:53

My original answer was for the case in the original question where the pairs slid along the diagonals rather than spreading across them with the first point staying anchored. While the solution is not exactly the same, the concept of computing indices in a vectorized manner applies here too.

Start with the matrix of row minus column which gives diagonals as before:

diag = np.arange(1, N) - np.arange(1, M)[:, None] + 2 * M - N

This shows that the the second element is given by

second = a[1:, 1:].ravel()[diag.argsort(None, kind='stable')]

The heads of the diagonals are the first column in reverse and the first row. If you index them correctly, you get the first element of each pair:

head = np.r_[a[::-1, 0], a[0, 1:]]
first = head[np.sort(diag, axis=None)]

Now you can just concatenate the result:

result = np.stack((first, second), axis=-1)

See: black magic! And totally vectorized.

How to select pairs of values in an array according to a given sequence for all matrix shapes?

4 Answers4