Получить все диагонали в матрице / списке списков в Python

Question

Я ищу Pythonic способ получить все диагонали (квадратной) матрицы, представленной в виде списка списков.

Предположим, у меня есть следующая матрица:

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

Возможно, есть лучшие способы сделать это в 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]]

Answer 2

Начните с диагоналей, которые наклонены вверх и вправо.

Если (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 3

Это для Moe, который задал аналогичный вопрос .

Я начинаю с создания простых функций для копирования строк или столбцов любой прямоугольной матрицы.

def get_rows(grid):
    return [[c for c in r] for r in grid]

def get_cols(grid):
    return zip(*grid)

С помощью этих двух функций я получаю диагонали, добавляя увеличивающийся / уменьшающийся буфер в начало / конец каждой строки.Затем я получаю столбцы этой буферизованной сетки, а затем удаляю буфер для каждого столбца.т.е.)

1 2 3    |X|X|1|2|3|    | | |1|2|3|
4 5 6 => |X|4|5|6|X| => | |4|5|6| | => [[7],[4,8],[1,5,9],[2,6],[3]]
7 8 9    |7|8|9|X|X|    |7|8|9| | |

.

def get_backward_diagonals(grid):
    b = [None] * (len(grid) - 1)
    grid = [b[i:] + r + b[:i] for i, r in enumerate(get_rows(grid))]
    return [[c for c in r if c is not None] for r in get_cols(grid)]

def get_forward_diagonals(grid):
    b = [None] * (len(grid) - 1)
    grid = [b[:i] + r + b[i:] for i, r in enumerate(get_rows(grid))]
    return [[c for c in r if c is not None] for r in get_cols(grid)]

Answer 4

Я столкнулся с другим интересным решением этой проблемы.Строка, столбец, прямая и обратная диагонали могут быть сразу обнаружены, если взглянуть на комбинацию 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]]

Answer 5

Я недавно изобрел это колесо. Вот простой в использовании / расширенный метод поиска диагоналей в квадратном списке списков:

def get_diagonals(grid, bltr = True):
  dim = len(grid)
  assert dim == len(grid[0])
  return_grid = [[] for total in xrange(2 * len(grid) - 1)]
  for row in xrange(len(grid)):
    for col in xrange(len(grid[row])):
      if bltr: return_grid[row + col].append(grid[col][row])
      else:    return_grid[col - row + (dim - 1)].append(grid[row][col])
  return return_grid

Предполагаемые индексы списка:

00 01 02 03

10 11 12 13

20 21 22 23

30 31 32 33

, затем установка bltr = True (по умолчанию), возвращает диагонали от левого нижнего к правому верхнему углу, т.е.

00           # row + col == 0
10 01        # row + col == 1
20 11 02     # row + col == 2
30 21 12 03  # row + col == 3
31 22 13     # row + col == 4
32 23        # row + col == 5
33           # row + col == 6

настройка bltr = False, возвращает диагонали от левого нижнего к верхнему правому углу, то есть

30            # (col - row) == -3
20 31         # (col - row) == -2
10 21 32      # (col - row) == -1
00 11 22 33   # (col - row) == 0
01 12 23      # (col - row) == +1
02 13         # (col - row) == +2
03            # (col - row) == +3

Вот работоспособная версия с использованием матрицы ввода OP.

Answer 6

Это работает только для матриц одинаковой ширины и высоты. Но это также не зависит от каких-либо третьих лиц.

matrix = [[11, 2, 4],[4, 5, 6],[10, 8, -12]]

# only works for diagnoals of equal width and height
def forward_diagonal(matrix):
    if not isinstance(matrix, list):
        raise TypeError("Must be of type list")

    results = []
    x = 0
    for k, row in enumerate(matrix):
        # next diag is (x + 1, y + 1)
        for i, elm in enumerate(row):

            if i == 0 and k == 0:
                results.append(elm)
                break
            if (x + 1 == i):
                results.append(elm)
                x = i
                break
    return results

print 'forward diagnoals', forward_diagonal(matrix)

Answer 7

Код, основанный на ответе Немо выше:

def print_diagonals(matrix):
    n = len(matrix)
    diagonals_1 = []  # lower-left-to-upper-right diagonals
    diagonals_2 = []  # upper-left-to-lower-right diagonals
    for p in range(2*n-1):
        diagonals_1.append([matrix[p-q][q] for q in range(max(0, p - n + 1), min(p, n - 1) + 1)])
        diagonals_2.append([matrix[n-p+q-1][q] for q in range(max(0, p - n + 1), min(p, n - 1) + 1)])
    print("lower-left-to-upper-right diagonals: ", diagonals_1)
    print("upper-left-to-lower-right diagonals: ", diagonals_2)


print_diagonals([
    [1, 2, 1, 1],
    [1, 1, 4, 1],
    [1, 3, 1, 6],
    [1, 7, 2, 5],
])

lower-left-to-upper-right diagonals:  [[1], [1, 2], [1, 1, 1], [1, 3, 4, 1], [7, 1, 1], [2, 6], [5]]
upper-left-to-lower-right diagonals:  [[1], [1, 7], [1, 3, 2], [1, 1, 1, 5], [2, 4, 6], [1, 1], [1]]