Trasformare le diagonali di matrice in matrice irregolare?

Question

Sto cercando di trovare una soluzione non a forza bruta al seguente problema. Data una matrice di dimensioni arbitrarie:

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

Trasforma le sue diagonali in un elenco di vettori, in questo modo:

(0)
(1, 2)
(3, 4, 5)
(6, 7, 8, 9)
(0, 1, 2)
(3, 4)
(5)

(Lavorando dall'angolo in basso a sinistra in alto a destra in questo esempio)

Esiste un modo elegante per eseguire questa breve sequenza di iterazioni nella colonna di sinistra e nella riga superiore?

Answer 1

Scriverei solo una piccola funzione per trasformare gli indici vettoriali in indici di matrice.

Supponi che la matrice sia NxN quadrata, quindi ci saranno 2N-1 ; se contiamo i vettori da 0 a 2N-2 , l'elemento k del vettore n sarà nella riga < codice> max (N-1-n + k, k) e colonna max (n + k-N + 1, k) (o al contrario, l'elemento matrice nella riga < code> i , la colonna j sarà l'elemento min (i, j) del vettore N-1 + ji ). Quindi, ogni volta che è necessario accedere a un elemento di un vettore, è sufficiente convertire le coordinate da k, n a i, j (ovvero convertire gli indici vettoriali in indici matrice) e accedere all'elemento appropriato della matrice. Invece di avere effettivamente un elenco di vettori, finirai con qualcosa che emula un elenco di vettori, nel senso che può darti qualsiasi elemento desiderato di qualsiasi vettore nell'elenco - che è davvero altrettanto buono. (Benvenuto nella battitura a papera ;-)

Se accederai a tutti gli elementi della matrice, tuttavia, potrebbe essere più veloce iterare, piuttosto che eseguire questo calcolo ogni volta.

Answer 2

(codice non controllato) Qualcosa del genere (codice Java):

// suppose m is the matrix, so basically an int[][] array with r rows and c columns
// m is an int[rows][cols];

List result = new ArrayList(rows + cols - 1);
for (int i = 0; i < (rows + cols - 1))
{
  int y;
  int x;
  if (i < rows)
  {
    x = 0;
    y = rows - i - 1;
  }
  else
  {
    x = i - rows + 1;
    y = 0;
  }
  Vector v = new Vector();
  while (y < rows && x < cols)
  {
    y++;
    x++;
    v.add(new Integer(m[y][c]));
  }
  result.add(v);
}
// result now contains the vectors you wanted

Modifica: avevo mischiato xey, corretto ora.

Answer 3

Mathematica:

m = {{6, 0, 3, 5}, 
     {3, 7, 1, 4}, 
     {1, 4, 8, 2}, 
     {0, 2, 5, 9}};

Table[Diagonal[m, i], {i, 1 - Length@m, Length@m[[1]] - 1}]

Che fornisce un elenco dell'ottava diagonale in cui la diagonale 0 è la diagonale principale, i = -1 indica quella sotto di essa, ecc. In altre parole, restituisce:

{{0}, {1, 2}, {3, 4, 5}, {6, 7, 8, 9}, {0, 1, 2}, {3, 4}, {5}}

Ovviamente usare la funzione Diagonal integrata è una specie di imbroglio. Ecco un'implementazione di Diagonal da zero:

(* Grab the diagonal starting from element (i,j). *)
diag0[m_,i_,j_] := Table[m[[i+k, j+k]], {k, 0, Min[Length[m]-i, Length@m[[1]]-j]}]

(* The i'th diagonal -- negative means below the main diagonal, positive above. *)
Diagonal[m_, i_] := If[i < 0, diag0[m, 1-i, 1], diag0[m, 1, i+1]]

La funzione Table è sostanzialmente un ciclo for che si raccoglie in un elenco. Ad esempio,

Table[2*i, {i, 1, 5}]

restituisce {2,4,6,8,10} .