Obtenez tous les diagonales dans une matrice/liste de listes en Python

Je suis à la recherche d'un Pythonic façon d'obtenir toutes les diagonales d'un carré) de la matrice, représenté par une liste de listes.

Supposons que j'ai la matrice suivante:

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

Puis les grandes diagonales sont faciles:

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]

Mais j'ai du mal à venir avec un moyen de générer toutes les diagonales. La sortie je suis à la recherche d'est:

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

InformationsquelleAutor BioGeek | 2011-06-11

Il y a probablement de meilleures façons de faire dans numpy que ci-dessous, mais je ne suis pas trop familier avec elle encore:

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]

De sortie

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

Modifier: mise à Jour de généraliser pour toute la taille de la matrice.

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]

De sortie

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

Je ne suis pas trop familier avec numpy soit. Soins pour expliquer comment cela fonctionne et comment vous pouvez vous la généraliser pour tout n*n de la matrice. Merci!
Mise à jour avec une explication.
Merci! Très utile et fonctionne comme un charme.
Merci! c'est génial.

InformationsquelleAutor Mark Tolonen

18

Commencer avec les diagonales que pente vers le haut-et-droit.

Si (x,y) est l'une de coordonnées rectangulaires à l'intérieur de la matrice, vous voulez transformer à partir d'un système de coordonnées (p,q), où p est le nombre de la diagonale et q est l'indice le long de la diagonale. (Si p=0, c'est la [-2] en diagonale, p=1, c'est la [9,5] en diagonale, p=2 est l' [3,-6,3] en diagonale, et ainsi de suite.)

De transformer une (p,q) dans un (x,y), vous pouvez utiliser:
```
x = q
y = p - q
```
Essayer de brancher les valeurs de p et q pour voir comment cela fonctionne.

Maintenant, vous venez de boucle... Pour p de 0 à 2N-1, et q à partir de max(0, p-N+1) min(p, N-1). Transformer p,q, x,y et imprimer.

Puis pour les autres diagonales, répétez les boucles, mais utiliser un autre transformation:
```
x = N - 1 - q
y = p - q
```
(Cela permet juste à l'inverse la matrice de gauche à droite.)

Désolé je n'ai pas fait ce code en Python. 🙂
- Voir ici pour un Python de mise en œuvre.
InformationsquelleAutor Nemo

C'est pour Moe, qui a demandé à une question similaire.

Je commence par faire simple les fonctions de copier des lignes ou des colonnes de toute matrice rectangulaire.

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

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

Avec ces deux fonctions, je puis obtenir les diagonales par l'ajout d'une augmentation/diminution de la mémoire tampon pour le début/la fin de chaque ligne. Je puis obtenir les colonnes de ce tampon de la grille, puis retirez le tampon sur chaque colonne par la suite. ie)

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

InformationsquelleAutor flakes

Je suis tombé sur une autre solution intéressante à ce problème.
La ligne, la colonne, vers l'avant et vers l'arrière en diagonale peut tous être immédiatement découvert en regardant une combinaison de x et de 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

À partir du diagramme, vous pouvez voir que chaque diagonale et de l'axe est uniquement identifiables à l'aide de ces équations. Prendre chaque numéro unique de chaque table et créer un conteneur pour identifiant.

Noter que l'arrière diagonales ont été compensés pour commencer à un index de zéro, et que la longueur de l'avant diagonales est toujours égale à la longueur de l'arrière diagonales.

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)

Qui permet d'imprimer

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

InformationsquelleAutor flakes

J'ai fini de réinventer la roue récemment. Voici une facile à réutiliser/étendre la méthode pour trouver les diagonales d'un carré liste de listes:

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

En supposant que la liste d'indices:

00 01 02 03

10 11 12 13

20 21 22 23

30 31 32 33

alors la configuration de la bltr = True (par défaut), renvoie les diagonales d'en bas à gauche à en haut à droite, c'est à dire

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

réglage bltr = False, renvoie les diagonales d'en bas à gauche à en haut à droite, c'est à dire

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

Voici une version exécutable à l'aide de l'OP de la matrice d'entrée.

InformationsquelleAutor Jedi

Cela ne fonctionne que pour matricies de la même largeur et la hauteur.
Mais il ne repose pas sur des tiers.

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)

InformationsquelleAutor willredington315

-1

Du Code sur la base de la Nemo réponse ci-dessus:

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

InformationsquelleAutor Martin

Vous devez vous connecter pour publier un commentaire.