Transformando diagonais da matriz para matriz irregular?

Question

Eu estou tentando chegar a uma solução não de força bruta para o seguinte problema. Dada uma matriz de tamanho arbitrário:

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

Transform suas diagonais a uma lista de vetores, assim:

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

(Trabalho de inferior esquerdo para canto superior direito, neste exemplo)

Existe uma maneira elegante de fazer isso curto de ficar repetindo-se a coluna esquerda e do outro lado da linha superior?

Answer 1

Gostaria apenas de escrever uma pequena função para transformar os índices vetoriais em índices matriciais.

Say a matriz é NxN quadrado, então haverá vectores 2N-1; se numerar os vectores de 0 para 2N-2, elemento k de n vector será em linha e max(N-1-n+k,k) max(n+k-N+1,k) coluna (ou no sentido inverso, o elemento de matriz em linha i, j coluna será elemento min(i,j) de N-1+j-i vector). Então sempre que você precisar acessar um elemento de um vetor, apenas converter as coordenadas de k,n para i,j (isto é, os índices de conversão vetor para índices matriciais) e acessar o elemento apropriado da matriz. Em vez de realmente ter uma lista de vetores, você vai acabar com algo que emula uma lista de vetores, no sentido de que ele pode lhe dar qualquer elemento desejado de qualquer vector na lista - que é realmente tão bom. (Bem-vindo ao tipagem pato; -)

Se você estiver indo para acessar cada elemento da matriz, porém, ele só poderia ser mais rápido para iterate, ao invés de fazer este cálculo de cada vez.

Answer 2

(não verificado código) Algo parecido com isto (código 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

Editar: eu tinha x e y misturados, corrigido agora

.

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

O que dá uma lista das diagonais i'ésima onde a diagonal 0 é a diagonal principal, i = -1 dá a uma por baixo, etc. Em outras palavras, ele retorna:

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

Claro que usando o built-in função Diagonal é uma espécie de batota. Aqui está uma implementação do Diagonal a partir do 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]]

A função Table é basicamente um loop que recolhe em uma lista. Por exemplo,

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

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