How to return an array of anti-diagonals or diagonals of given N*N square matrix

Viewed 3053

I need to print the diagonals of matrix

  • if diagonals then i to i + 1 and j to j -1
  • if anti-diagonals then i to i-1 and j to j + 1

matrix is

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

Expected out is

1 0 0
2 4 0
3 5 7 
6 8 0
9 0 0

Code is below for diagonal

def print_diagonal(A):
    

    m = len(A)
    n = len(A[0])
    #result = [[0 for i in range(m)] for i in range(n)]
    result = []
    for k in range(m):
        i = k
        j = 0
        while i>=0:
            result.append(A[i][j])
            i = i -1
            j = j + 1
    for k in range(1,n):       
        i = m - 1
        j = k
        while (j <= n-1):
            result.append(A[i][j])
            i = i -1
            j = j + 1
    return result
        
A = [[1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]]
print_diagonal(A)

My output is

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

The numbers in my output is matching correctly, but its not coming in order as expected

4 Answers

Just create a matrix of 0s and then fill the diagonals one by one:

def print_diagonal(A):
    m = len(A)
    result = [[0]*m for _ in range(2*m-1)]
    for i in range(m):
        for k in range(i+1):
            result[i][k] = A[k][i-k]
    for i in range(0,m-1):
        for k in range(m-1-i):
            result[m+i][k] = A[i+k+1][m-1-k]
    return result

The order of iteration was wrong, you were going from the bottom-left to the top-right each time. Also the length to fill with zeroes is based on the minimum of n and m since n or m can only be decreased at most min(n, m) times before it reaches 0.

def print_diagonal(A):
    
    n = len(A)
    m = len(A[0])
    result = []
    length = min(n, m)

    # Top-left to top-right
    for k in range(m):
        result.append([0 for _ in range(length)])
        i = 0
        j = k
        while j >= 0 and i < n:
            result[-1][i] = A[i][j]
            i = i + 1
            j = j - 1

    # Top-right to bottom-right
    for k in range(1,n): 
        result.append([0 for _ in range(length)])      
        i = k
        j = m - 1
        while j >= 0 and i < n:
            result[-1][i - k] = A[i][j]
            i = i + 1
            j = j - 1
    return result
        
A = [[1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]]
print(print_diagonal(A))

prints out [[1, 0, 0], [2, 4, 0], [3, 5, 7], [6, 8, 0], [9, 0, 0]].

The following algorithm takes advantage of the fact that the diagonals of a matrix are simply every (n-1)th element when iterating the columns of an nxn matrix from left to right and top to bottom and restricting the result to one element per row. I wrote the programme for a similar case, but omitting the leading zeros. However, I added the necessary rows to add fills. To work with nxm matrices as well, some adjustments are necessary.

def print_diagonal(A, zeros=True):
    Al = np.concatenate(A)
    d = max(np.array(A).shape)
    results = []
    for start in range(0, 2 * d - 1):
        line = []
        row = max(start - d + 1, 0)
        p = start if row == 0 else (row + 1) * d - 1
        while np.floor(p / d) == row and p < len(Al):
            line.append(Al[p])
            p = p + d - 1
            row += 1

        if zeros and len(line) < d:
            line = [0] * (d - len(line)) + line if start < d else line + [0] * (d - len(line)) 

        results.append(line)
    return results

Given your example, the algorith has the following output:

print_diagonal(A, zeros=False) # [[1], [2, 4], [3, 5, 7], [6, 8], [9]]
print_diagonal(A, zeros=True)  # [[0, 0, 1], [0, 2, 4], [3, 5, 7], [6, 8, 0], [9, 0, 0]]

You could make a function that extracts the first row and last columns (outer edge) to form the first elements in the diagonals, then repeat the process iteratively on the remaining sub-matrix padding with leading&trailing zeroes and adding elements to the diagonals at each iteration:

def diagsDownLeft(M):
    diags,pad = [],[]
    while any(M):
        edge   = [*M[0][:-1] ,*next(zip(*map(reversed,M)))]
        M      = [r[:-1] for r in M[1:]]
        diags.append(pad+edge+pad)
        pad.append(0)        
    return [*map(list,zip(*diags))]

Output (for any rectangular matrix):

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

print(diagsDownLeft(A))
[[1, 0, 0], [2, 4, 0], [3, 5, 7], [6, 8, 0], [9, 0, 0]]

B = [[1, 2, 3, 10],
     [4, 5, 6, 11],
     [7, 8, 9, 12]]

print(diagsDownLeft(B))
[[1, 0, 0], [2, 4, 0], [3, 5, 7], [10, 6, 8], [11, 9, 0], [12, 0, 0]]


C = [[1,  2,  3],
     [4,  5,  6],
     [7,  8,  9],
     [10, 11, 12]]

print(diagsDownLeft(C))
[[1, 0, 0], [2, 4, 0], [3, 5, 7], [6, 8, 10], [9, 11, 0], [12, 0, 0]]

How it works (visually):

    1 2 3  1 2 3
    4 5 6  x x 6
    7 8 9  x x 9  ==> 1 2 3 6 9  (pad = none)
                      | | | | |
    4 5    4 5        | | | | |
    7 8    x 8    ==> 0 4 5 8 0  (pad = 0)
                      | | | | |
    7      7      ==> 0 0 7 0 0  (pad = 0,0)
                      | | | | |
                      \ \ \ \ \__ [9,0,0]     zipped
                       \ \ \ \___ [6,8,0]
                        \ \ \____ [3,5,7]
                         \ \_____ [2,4,0]
                          \______ [1,0,0]

If you also need the other diagonals:

def diagsDownRight(M):
    diags,pad = [],[]
    while any(M):
        edge = [*next(zip(*reversed(M))), *M[0][1:]]
        M    = [r[1:] for r in M[1:]]
        diags.append(pad+edge+pad)
        pad.append(0)        
    return [*map(list,zip(*diags))]

Output:

print(diagsDownRight(A))
[[7, 0, 0], [4, 8, 0], [1, 5, 9], [2, 6, 0], [3, 0, 0]]

print(diagsDownRight(B))
[[7, 0, 0], [4, 8, 0], [1, 5, 9], [2, 6, 12], [3, 11, 0], [10, 0, 0]]

print(diagsDownRight(C))
[[10, 0, 0], [7, 11, 0], [4, 8, 12], [1, 5, 9], [2, 6, 0], [3, 0, 0]]

And opposite directions:

def diagsUpRight(M):
    diags,pad = [],[]
    while any(M):
        edge = [*next(zip(*M)), *M[-1][1:]]
        M    = [r[1:] for r in M[:-1]]
        diags.append(pad+edge+pad)
        pad.append(0)        
    return [*map(list,zip(*diags))]

def diagsUpLeft(M):
    diags,pad = [],[]
    while any(M):
        edge = [*M[-1][:-1],*next(zip(*map(reversed,M[::-1])))]
        M    = [r[:-1] for r in M[:-1]]
        diags.append(pad+edge+pad)
        pad.append(0)        
    return [*map(list,zip(*diags))]
Related