Получение диагоналей в матрице. Алгоритм

Одна из причин, почему я захотел написать строчки насчет этого алгоритма, так как сам в большинстве случаев находил лишь вариант решения с numPy. Это, безусловно, отличная библиотека, но все же интересен сам алгоритм для использования в различных целях. Ну а начать, пожалуй, хочется с минимальным количеством воды, поэтому сразу начну с объяснения метода.



Очевидное, что приходит в голову, что если «продлить» диагонали, или же, другими словами, представить диагонали в виде набора элементов, то количество тех самых элементов будет равно, но не все матрицы будут заполнены «по максимуму». Посмотрим на изображение 1, в котором числами сверху отмечены номера диагоналей и они проведены через элементы таблицы чисел. Не трудно осознать, что количество таких диагоналей равно $inline$N + M - 1$inline$, где N — количество строк в таблице, а M — количество столбцов в таблице. Пускай номера диагоналей, чье начало начинается с отсутствия элементов, обозначим зеленым цветом для удобства понимания.

В голову напрашивается очевидный вариант, как можно получить все диагонали с их элементами. А точнее, перебрать $inline$N + M - 1$inline$, в начале пусто заполненных, диагоналей и заполнить их соответствующими элементами. Перебирать будем в диапазоне

$$display$$[-(N - 1); M)$$display$$

, поскольку все числа, какие будут «с минусом» в данном диапазоне будет, как раз, равно кол-ву диагоналям, чье начало идет с «пустыми элементами», а точнее вообще без ничего и будет равно кол-ву $inline$N - 1 = (N + M - 1 - M)$inline$. Удобно использовать в реализации.

diagonals = [[] for i in range(N + M - 1)]
for i in range(-(N - 1), M):
....

Изображение 1

Соображение №1

Давайте выясним, как можно заполнить нужными элементами. Для начала вспомним, что элементы главной диагонали подчиняются правилу, что индекс позиции элемента a (= a[i][i]), где i — номер столбца и строки соответственно. Теперь можно обратить внимание, что другие безымянные диагонали отличаются лишь позицией лишь началом «отсчёта». В общем виде каждый $inline$i$inline$-овый элемент дополнительных диагоналей, параллельных главной диагонали, можно выразить так: $inline$b[i] = a[i][i + j]$inline$, $inline$b$inline$ — набор элементов диагонали, где $inline$i$inline$ — номер элемента, $inline$j$inline$ — «коэффициент отклонения диагонали», то есть на сколько столбец уходит в сторону от нулевого. Влево, вправо — неважно. И также, безусловно, условия, чтобы не выходить за границы.
Получаем:

$$display$$\begin{cases} b[i] = a[i][i + j], &\text{где $i$ - это номер элемента в $j + N - 1$ диагонали, $a$ - исходная матрица} \\ 0 <= i < n \\ 0 <= i + j < m \end{cases}$$display$$

То есть достаточно добавить до N элементов в набор каждой диагонали. Отметим, что если индекс выходит за границы размера таблицы, то элемент явно не является частью набор любой диагонали. Также поскольку номер позиции каждого элемента диагонали = номеру строки, в которой он находится, то значение некому row присвоим j. Столбец (col), можно понять, что равен i + j, исходя из соображения под номером (1). Нам остается лишь обязательно учитывать границы row и col, дабы избежать выхода из границ существующих элементов для наших диагоналей.

diagonals = [[] for i in range(N + M - 1)]
for i in range(-(N - 1), M):
    for j in range(N):
        row, col = j, i + j
        if 0 <= row < len(matrix) and 0 <= col < len(matrix[0]):
            diagonals[i + len(matrix) - 1].append(matrix[row][col])

Также этот алгоритм можно немного изменить, чтобы проделать процесс относительно диагоналей, параллельных побочной диагонали, изменив лишь эту строчку таким образом:

diagonals[i + len(matrix) - 1].append(matrix[row][M - col - 1])

На этом в принципе все. Нетрудный для понимания алгоритм поможет найти все диагонали в матрице.