Get All the Diagonals in a Matrix/List of Lists in Python

Python 3: Get diagonal elements of matrix (list of lists) about a point in that matrix without NumPy

A bit confusing, but I think this does it:

def getDiagonals(matrix, pos):
    row, col = pos
    nrows = len(matrix)
    ncols = len(matrix[0]) if nrows > 0 else 0
    # First diagonal
    d1_i, d1_j = nrows - 1 - max(row - col, 0), max(col - row, 0)
    d1_len = min(d1_i + 1, ncols - d1_j)
    diag1 = [matrix[d1_i - k][d1_j + k] for k in range(d1_len)]
    # Second diagonal
    t = min(row, ncols - col - 1)
    d2_i, d2_j = nrows - 1 - row + t, col + t
    d2_len = min(d2_i, d2_j) + 1
    diag2 = [matrix[d2_i - k][d2_j - k] for k in range(d2_len)]
    return (diag1, diag2)

# Test
matrix = [[0, 0, 0, 0, 5],
          [0, 0, 0, 4, 0],
          [2, 0, 3, 0, 0],
          [3, 2, 0, 2, 0],
          [1, 0, 2, 0, 1]]
diagonals = getDiagonals(matrix, (1, 1))
print(diagonals[0])
# [1, 2, 3, 4, 5]
print(diagonals[1])
# [2, 2, 2]

diagonals = getDiagonals(matrix, (1, 3))
print(diagonals[0])
# [2, 2, 0]
print(diagonals[1])
# [1, 2, 3, 0, 0]

diagonals = getDiagonals(matrix, (2, 2))
print(diagonals[0])
# [1, 2, 3, 4, 5]
print(diagonals[1])
# [1, 2, 3, 0, 0]

Get all the diagonals in a matrix/list of lists in Python

There are probably better ways to do it in numpy than below, but I'm not too familiar with it yet:

import numpy as np

matrix = np.array(
         [[-2,  5,  3,  2],
          [ 9, -6,  5,  1],
          [ 3,  2,  7,  3],
          [-1,  8, -4,  8]])

diags = [matrix[::-1,:].diagonal(i) for i in range(-3,4)]
diags.extend(matrix.diagonal(i) for i in range(3,-4,-1))
print [n.tolist() for n in diags]

Output

[[-2], [9, 5], [3, -6, 3], [-1, 2, 5, 2], [8, 7, 1], [-4, 3], [8], [2], [3, 1], [5, 5, 3], [-2, -6, 7, 8], [9, 2, -4], [3, 8], [-1]]

---

Edit: Updated to generalize for any matrix size.

import numpy as np

# Alter dimensions as needed
x,y = 3,4

# create a default array of specified dimensions
a = np.arange(x*y).reshape(x,y)
print a
print

# a.diagonal returns the top-left-to-lower-right diagonal "i"
# according to this diagram:
#
#  0  1  2  3  4 ...
# -1  0  1  2  3
# -2 -1  0  1  2
# -3 -2 -1  0  1
#  :
#
# You wanted lower-left-to-upper-right and upper-left-to-lower-right diagonals.
#
# The syntax a[slice,slice] returns a new array with elements from the sliced ranges,
# where "slice" is Python's [start[:stop[:step]] format.

# "::-1" returns the rows in reverse. ":" returns the columns as is,
# effectively vertically mirroring the original array so the wanted diagonals are
# lower-right-to-uppper-left.
#
# Then a list comprehension is used to collect all the diagonals.  The range
# is -x+1 to y (exclusive of y), so for a matrix like the example above
# (x,y) = (4,5) = -3 to 4.
diags = [a[::-1,:].diagonal(i) for i in range(-a.shape[0]+1,a.shape[1])]

# Now back to the original array to get the upper-left-to-lower-right diagonals,
# starting from the right, so the range needed for shape (x,y) was y-1 to -x+1 descending.
diags.extend(a.diagonal(i) for i in range(a.shape[1]-1,-a.shape[0],-1))

# Another list comp to convert back to Python lists from numpy arrays,
# so it prints what you requested.
print [n.tolist() for n in diags]

Output

[[ 0  1  2  3]
 [ 4  5  6  7]
 [ 8  9 10 11]]

[[0], [4, 1], [8, 5, 2], [9, 6, 3], [10, 7], [11], [3], [2, 7], [1, 6, 11], [0, 5, 10], [4, 9], [8]]

How to get all the diagonal two-dimensional list without using numpy?

Try this. Define variables COL and ROW and then run the following function with your matrix.

def diagonalOrder(matrix) :       
    # There will be ROW+COL-1 lines in the output   
    for line in range(1, (ROW + COL)) :   
        # Get column index of the first element  
        # in this line of output. The index is 0   
        # for first ROW lines and line - ROW for   
        # remaining lines    
        start_col = max(0, line - ROW) 

        # Get count of elements in this line. 
        # The count of elements is equal to  
        # minimum of line number, COL-start_col and ROW     
        count = min(line, (COL - start_col), ROW) 

        # Print elements of this line     
        for j in range(0, count) :   
            print(matrix[min(ROW, line) - j - 1]   
                        [start_col + j], end = "\t")   
        print() 

Finding all elements below the big diagonal of a matrix

This is one way you can achieve that result:

matrix = [['a', 'p', 'p', 'l', 'e'],
          ['a', 'g', 'o', 'd', 'o'],
          ['n', 'n', 'e', 'r', 't'],
          ['g', 'a', 'T', 'A', 'C'],
          ['m', 'i', 'c', 's', 'r'],
          ['P', 'o', 'P', 'o', 'P']]
my_list = []
for f in range(1, len(matrix[0])):
    s = []
    for k in range(len(matrix[0]) - f):
        s.append(matrix[len(matrix) - k - 1][f + k])
    my_list.append(''.join(s))
print(my_list)
# ['ocAt', 'PsC', 'or', 'P']

Or using comprehension:

my_list = [''.join(matrix[len(matrix) - i - 1][j + i] for i in range(len(matrix[0]) - j))
           for j in range(1, len(matrix[0]))]

---

To produce every substring in each diagonal you can do:

my_list = []
for j in range(1, len(matrix[0])):
    for i1 in range(0, len(matrix[0]) - j):
        for i2 in range(i1 + 1, len(matrix[0]) - j + 1):
            s = []
            for i in range(i1, i2):
                s.append(matrix[len(matrix) - i - 1][j + i])
            my_list.append(''.join(s))
print(my_list)
# ['o', 'oc', 'ocA', 'ocAt', 'c', 'cA', 'cAt', 'A', 'At', 't', 'P', 'Ps', 'PsC', 's', 'sC', 'C', 'o', 'or', 'r', 'P']

Or equivalently:

my_list = [''.join(matrix[len(matrix) - i - 1][j + i] for i in range(i1, i2))
           for j in range(1, len(matrix[0]))
           for i1 in range(0, len(matrix[0]) - j)
           for i2 in range(i1 + 1, len(matrix[0]) - j + 1)]

--

One solution for substrings in upper diagonals:

my_list = []
for i in range(len(matrix)):
    for j1 in range(min(i + 1, len(matrix[0]))):
        for j2 in range(j1, min(i + 1, len(matrix[0]))):
            s = []
            for j in range(j1, j2 + 1):
                s.append(matrix[i - j][j])
            my_list.append(''.join(s))
print(my_list)
# ['a', 'a', 'ap', 'p', 'n', 'ng', 'ngp', 'g', 'gp', 'p', 'g',
#  'gn', 'gno', 'gnol', 'n', 'no', 'nol', 'o', 'ol', 'l', 'm',
#  'ma', 'mae', 'maed', 'maede', 'a', 'ae', 'aed', 'aede', 'e',
#  'ed', 'ede', 'd', 'de', 'e', 'P', 'Pi', 'PiT', 'PiTr', 'PiTro',
#  'i', 'iT', 'iTr', 'iTro', 'T', 'Tr', 'Tro', 'r', 'ro', 'o']

Find diagonals in a Python matrix using lists

If you consider the logic of your 'right-to-left' loop, you are actually just doing the same as your 'left-to-right' loop in reverse order. To really get the 'right-to-left' pass right you have to have your i and j indices moving in different directions.

So your conditional statement in this section should look like:

if i-3>=0 and j+3<7:
    if (llista[i][j]==1 and llista[i-1][j+1]==1 and llista[i-2][j+2]==1 and llista[i-3][j+3]==1)  or (llista[i][j]==2 and llista[i-1][j+1]==2 and llista[i-2][j+2]==2 and llista[i-3][j+3]==2 ):
        print("There is at least one right to left diagonal")

There are a ton of optimizations you could use by importing libraries like numpy or itertools as AResem showed. That answer is not entirely correct though for the following reason.

When you say return True, k you are not exercising any control over the value of k because it was used in the list comprehension just above and will just have the value of the last item it iterated over. So when your function finds a diagonal it reports the wrong number about two thirds of the time.

Here is an edited function that gives the correct results:

def check_diagonals(matrix):
    for offset in range(-2, 4):
        diag = matrix.diagonal(offset=offset)

        # Here you can create a tuple of numbers with the number of times they are repeated. 
        # This allows you to keep your k and g values associated.
        repeat_groups = [(k, sum(1 for _ in g)) for k, g in  groupby(diag)]

        # By using the built-in max function with the 'key' keyword, you can find 
        # the maximum number of repeats and return the number associated with that.
        num, max_repeats = max(repeat_groups, key=lambda item: item[1])
        if max_repeats >= 4:
            return True, num
    return False, None

If you run this function with print statements added you can get output like the following:

Matrix: 
[[1 0 2 2 1 0 1]
 [0 2 0 2 1 1 1]
 [2 2 0 0 0 0 1]
 [0 0 2 2 0 2 2]
 [2 1 1 1 1 1 0]
 [2 2 0 2 1 0 2]]

offset -2
diag [2 0 1 2]
repeat_groups [(2, 1), (0, 1), (1, 1), (2, 1)]
num, max_repeats 2 1

offset -1
diag [0 2 2 1 1]
repeat_groups [(0, 1), (2, 2), (1, 2)]
num, max_repeats 2 2

offset 0
diag [1 2 0 2 1 0]
repeat_groups [(1, 1), (2, 1), (0, 1), (2, 1), (1, 1), (0, 1)]
num, max_repeats 1 1

offset 1
diag [0 0 0 0 1 2]
repeat_groups [(0, 4), (1, 1), (2, 1)]
num, max_repeats 0 4
(True, 0)
There is at least one left to right diagonal: 0's' # Correct!

If you want to ignore diagonals of zeros, you can easily add an extra condition, e.g.

if max_repeats >= 4 and num != 0:
    return True, num

You could try and recreate this without using numpy if you wanted.

Pythonic way to check diagonals in nested list

You can start by thinking of a means of naming the diagonals. For example, in a 3x3 matrix the indices (x, y) go like this:

(0,0) (1,0) (2,0)
(0,1) (1,1) (2,1)
(0,2) (1,2) (2,2)

If we follow the diagonals, their indices have a simple pattern. The diagonals that run lower left to upper right are:

Diag #1 (0,0)
Diag #2 (0,1) (1,0)
Diag #3 (0,2) (1,1) (2,0)
Diag #4 (1,2) (2,1)
Diag #5 (2,2)

From upper left to lower right they are:

#1 (0,2)
#2 (0,1) (1,2)
#3 (0,0) (1,1) (2,2)
#4 (1,0) (2,1)
#5 (2,0)

Notice that in the lower left to upper right case, every cell (x, y) on the same diagonal has the same value of x + y. In the other case, every cell on the same diagonal has the same value of x - y. Obviously this will be true for any size matrix. We can use x+y and x-y to name the individual diagonals. As we step through the matrix, each time we encounter a "1" we can immediately calculate the names of the two diagonals that intersect there.

This suggests an efficient algorithm for deciding if any two "1"s are on the same diagonal. In Python we can use two sets to keep track of the "occupied" diagonals. If we encounter a "1" on an already-occupied diagonal, we return True, otherwise false. We can step through the matrix in any order provided we visit all the elements.

def has_diagonal_ones(a):
    # a is a 2-dimensional square array of 0's and 1's
    lower_left_upper_right = set()
    upper_left_lower_right = set()
    for x in range(len(a)):
         for y in range(len(a)):
             if a[x][y] == 0:
                 continue
             i_lower_to_upper = x + y
             i_upper_to_lower = x - y
             if i_lower_to_upper in lower_left_upper_right:
                 return True
             if i_upper_to_lower in upper_left_lower_right:
                 return True
             lower_left_upper_right.add(i_lower_to_upper)
             upper_left_lower_right.add(i_upper_to_lower) 
    return False

L = [[1, 0, 1],
 [0, 0, 0],
 [0, 0, 1]]
print(has_diagonal_ones(L))

>>> True

How to get the diagonals of all rows in a 2D numpy array?

Well it seems like a specialized case of keeping diagonal elements. Here's one vectorized solution using masking -

def keep_diag(a):    
    m,n = a.shape
    i,j = np.ogrid[:m,:n]
    mask = (i>=j) & ((i-m+n)<=j)
    return a.T[mask.T].reshape(n,-1).T

Most of the trick is at the step of mask creation, which when masked with the input array gets us the required elements off it.

Sample runs -

In [105]: a
Out[105]: 
array([[ 0, 16],
       [11, 98],
       [81, 63],
       [83, 20]])

In [106]: keep_diag(a)
Out[106]: 
array([[ 0, 98],
       [11, 63],
       [81, 20]])

In [102]: a
Out[102]: 
array([[10,  2, 66],
       [44, 18, 35],
       [70,  8, 31],
       [12, 27, 86]])

In [103]: keep_diag(a)
Out[103]: 
array([[10, 18, 31],
       [44,  8, 86]])

---

Related Topics