在Python中获取矩阵/列表的所有对角线

Question

我想找一种Python风格的方法来获取一个（方形）矩阵的所有对角线，这个矩阵是用列表的列表来表示的。

假设我有以下这个矩阵：

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

那么大的对角线很简单：

l = len(matrix[0])
print([matrix[i][i] for i in range(l)])              # [-2, -6, 7,  8]
print([matrix[l-1-i][i] for i in range(l-1,-1,-1)])  # [ 2,  5, 2, -1]

但是我在想怎么生成所有的对角线时遇到了困难。我想要的输出是：

[[-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]]

Answer 1

首先，从向右上方倾斜的对角线开始。

如果 (x,y) 是矩阵中的一个矩形坐标，你想要转换成一个坐标系统 (p,q)，其中 p 是对角线的编号，q 是在这条对角线上的索引。比如说，p=0 是 [-2] 这条对角线，p=1 是 [9,5] 这条对角线，p=2 是 [3,-6,3] 这条对角线，依此类推。

要把 (p,q) 转换成 (x,y)，你可以使用：

x = q
y = p - q

试着代入一些 p 和 q 的值，看看这个是怎么工作的。

现在你只需要循环... 对于 p 从 0 到 2N-1，q 从 max(0, p-N+1) 到 min(p, N-1)。然后把 p,q 转换成 x,y 并打印出来。

接下来，对于其他的对角线，重复这个循环，但使用不同的转换方式：

x = N - 1 - q
y = p - q

（这实际上只是把矩阵左右翻转了一下。）

抱歉我没有用 Python 实际编写这个代码。:-)

Answer 2

我发现了一个有趣的解决方案来处理这个问题。通过结合 x 和 y 的值，我们可以很快找到行、列、正对角线和反对角线。

Column = x     Row = y        F-Diag = x+y   B-Diag = x-y     B-Diag` = x-y-MIN 
  | 0  1  2      | 0  1  2      | 0  1  2      | 0  1  2        | 0  1  2     
--|---------   --|---------   --|---------   --|---------     --|---------    
0 | 0  1  2    0 | 0  0  0    0 | 0  1  2    0 | 0  1  2      0 | 2  3  4     
1 | 0  1  2    1 | 1  1  1    1 | 1  2  3    1 |-1  0  1      1 | 1  2  3     
2 | 0  1  2    2 | 2  2  2    2 | 2  3  4    2 |-2 -1  0      2 | 0  1  2     

从图示中可以看出，每条对角线和轴线都可以通过这些公式唯一识别。我们可以从每个表中提取出每个独特的数字，并为这些标识符创建一个容器。

需要注意的是，反对角线的起始位置是从零开始的，而正对角线的长度总是等于反对角线的长度。

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

max_col = len(test[0])
max_row = len(test)
cols = [[] for _ in range(max_col)]
rows = [[] for _ in range(max_row)]
fdiag = [[] for _ in range(max_row + max_col - 1)]
bdiag = [[] for _ in range(len(fdiag))]
min_bdiag = -max_row + 1

for x in range(max_col):
    for y in range(max_row):
        cols[x].append(test[y][x])
        rows[y].append(test[y][x])
        fdiag[x+y].append(test[y][x])
        bdiag[x-y-min_bdiag].append(test[y][x])

print(cols)
print(rows)
print(fdiag)
print(bdiag)

这段代码将会输出

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

---

使用 defaultdict 和 lambda 函数，我们可以进一步将这个方法进行通用化：

from collections import defaultdict


def groups(data, func):
    grouping = defaultdict(list)
    for y in range(len(data)):
        for x in range(len(data[y])):
            grouping[func(x, y)].append(data[y][x])
    return list(map(grouping.get, sorted(grouping)))


test = [[1, 2, 3], [4, 5, 6], [7, 8, 9], [10, 11, 12]]
cols = groups(test, lambda x, y: x)
rows = groups(test, lambda x, y: y)
fdiag = groups(test, lambda x, y: x + y)
bdiag = groups(test, lambda x, y: x - y)

Answer 3

在 numpy 中，可能有更好的方法来实现这个功能，但我对它还不太熟悉：

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]

输出结果

[[-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]]

---

编辑: 更新了代码，使其适用于任何大小的矩阵。

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]

输出结果

[[ 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]]