c - Traverse Matrix en tiras diagonales
algorithm traversal (16)
Pensé que este problema tenía una solución trivial, un par de bucles for y algunos contadores de lujo
Precisamente.
Lo importante de notar es que si le das a cada ítem un índice ( i , j ) entonces los ítems en la misma diagonal tienen el mismo valor j + n - i , donde n es el ancho de tu matriz. Por lo tanto, si itera sobre la matriz de la forma habitual (es decir, bucles anidados sobre i y j ), puede realizar un seguimiento de las diagonales en una matriz que se trata de la manera mencionada anteriormente.
Pensé que este problema tenía una solución trivial, un par de bucles for y algunos contadores de lujo, pero aparentemente es bastante más complicado.
Entonces mi pregunta es, ¿cómo escribirías (en C) una función transversal de una matriz cuadrada en tiras diagonales?
Ejemplo:
1 2 3
4 5 6
7 8 9
Debería atravesarse en el siguiente orden:
[1],[2,4],[3,5,7],[6,8],[9]
Cada tira de arriba está encerrada entre corchetes. Uno de los requisitos es poder distinguir entre tiras. Lo que significa que sabes cuándo estás comenzando una nueva tira. Esto porque hay otra función que debo llamar para cada elemento en una tira y luego antes del comienzo de una nueva tira. Por lo tanto, una solución sin duplicación de código es ideal.
// Este algoritmo funciona para matrices de todos los tamaños. ;)
int x = 0;
int y = 0;
int sub_x;
int sub_y;
while (true) {
sub_x = x;
sub_y = y;
while (sub_x >= 0 && sub_y < y_axis.size()) {
this.print(sub_x, sub_y);
sub_x--;
sub_y++;
}
if (x < x_axis.size() - 1) {
x++;
} else if (y < y_axis.size() - 1) {
y++;
} else {
break;
}
}
Aquí hay algo que puedes usar. Simplemente reemplace los printfs con lo que realmente quiere hacer.
#include <stdio.h>
int main()
{
int x[3][3] = {1, 2, 3,
4, 5, 6,
7, 8, 9};
int n = 3;
for (int slice = 0; slice < 2 * n - 1; ++slice) {
printf("Slice %d: ", slice);
int z = (slice < n) ? 0 : slice - n + 1;
for (int j = z; j <= slice - z; ++j) {
printf("%d ", x[j][slice - j]);
}
printf("/n");
}
return 0;
}
Salida:
Slice 0: 1
Slice 1: 2 4
Slice 2: 3 5 7
Slice 3: 6 8
Slice 4: 9
Cambiaría las filas así:
1 2 3 x x
x 4 5 6 x
x x 7 8 9
Y solo itera las columnas. Esto realmente se puede hacer sin cambios físicos.
Creo que esto puede ser una solución para cualquier tipo de matriz.
#include <stdio.h>
#define M 3
#define N 4
main(){
int a[M][N] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9,10,11,12}};
int i, j, t;
for( t = 0; t<M+N; ++t)
for( i=t, j=0; i>=0 ; --i, ++j)
if( (i<M) && (j<N) )
printf("%d ", a[i][j]);
return 0;
}
Echemos un vistazo cómo los elementos de la matriz están indexados.
(0,0) (0,1) (0,2) (0,3) (0,4)
(1,0) (1,1) (1,2) (1,3) (1,4)
(2,0) (2,1) (2,2) (2,3) (2,4)
Ahora, echemos un vistazo a las rayas:
Stripe 1: (0,0)
Stripe 2: (0,1) (1,0)
Stripe 3: (0,2) (1,1) (2,0)
Stripe 4: (0,3) (1,2) (2,1)
Stripe 5: (0,4) (1,3) (2,2)
Stripe 6: (1,4) (2,3)
Stripe 7: (2,4)
Si miras más de cerca, notarás una cosa. La suma de los índices de cada elemento de la matriz en cada banda es constante. Entonces, aquí está el código que hace esto.
public static void printSecondaryDiagonalOrder(int[][] matrix) {
int rows = matrix.length;
int cols = matrix[0].length;
int maxSum = rows + cols - 2;
for (int sum = 0; sum <= maxSum; sum++) {
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (i + j - sum == 0) {
System.out.print(matrix[i][j] + "/t");
}
}
}
System.out.println();
}
}
No es el algoritmo más rápido que existe (hace (rows * cols * (rows + cols-2)) operaciones), pero la lógica detrás de él es bastante simple.
En caso de que alguien necesite hacer esto en python, es muy fácil usar numpy:
#M is a square numpy array
for i in range(-M.shape[0]+1, M.shape[0]):
print M.diagonal(offset=i)
Encontré esto aquí: Traverse Rectangular Matrix in Diagonal strips
#include <stdio.h>
int main()
{
int x[3][4] = { 1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12};
int m = 3;
int n = 4;
for (int slice = 0; slice < m + n - 1; ++slice) {
printf("Slice %d: ", slice);
int z1 = slice < n ? 0 : slice - n + 1;
int z2 = slice < m ? 0 : slice - m + 1;
for (int j = slice - z2; j >= z1; --j) {
printf("%d ", x[j][slice - j]);
}
printf("/n");
}
return 0;
}
salida:
Slice 0: 1
Slice 1: 5 2
Slice 2: 9 6 3
Slice 3: 10 7 4
Slice 4: 11 8
Slice 5: 12
Me pareció una manera bastante elegante de hacerlo, ya que solo necesita memoria para 2 variables adicionales (z1 y z2), que básicamente contienen la información sobre la longitud de cada segmento. El bucle externo se mueve a través de los números de corte ( slice ) y el bucle interno se mueve a través de cada corte con índice: slice - z1 - z2 . Toda la demás información que necesita, entonces, dónde comienza el algoritmo y cómo se mueve a través de la matriz. En el ejemplo anterior, se desplazará hacia abajo en la matriz primero, y luego de llegar al final se moverá hacia la derecha: (0,0) -> (1,0) -> (2,0) -> (2,1) - > (2,2) -> (2,3). De nuevo, este patrón es capturado por los varibales z1 y z2. La fila se incrementa junto con el número de slice hasta que llegue al final, luego z2 comenzará a incrementarse, lo que se puede usar para mantener el índice de fila constante en su posición: slice - z2 . La longitud de cada corte se conoce por: slice - z1 - z2 , que muestra lo siguiente: (slice - z2) - (slice - z1 -z2) (menos cuando el algoritmo se mueve en orden ascendente m--, n ++) da como resultado z1 que es el criterio de detención para el ciclo interno. Solo queda el índice de columna que se hereda convenientemente del hecho de que j es constante después de llegar al final, después del cual el índice de columna comienza a incrementarse.
El algoritmo precedente se mueve solo en orden ascendente de izquierda a derecha comenzando en la parte superior izquierda (0,0). Cuando necesité este algoritmo, también tuve que buscar a través de una matriz en orden descendente empezando por la parte inferior izquierda (m, n). Como el algoritmo me encantó, decidí llegar al fondo y adaptarlo:
- La longitud de corte se conoce nuevamente por:
slice -z1 - z2 - La posición de inicio de las rodajas son: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
- El movimiento de cada segmento es m ++ y n ++
Lo encontré bastante útil para describirlo de la siguiente manera:
- slice = 0 z1 = 0 z2 = 0 (2,0) (índice de la columna = rowindex - 2)
- slice = 1 z1 = 0 z2 = 0 (1,0) (2,1) (índice de la columna = rowindex - 1)
- slice = 2 z1 = 0 z2 = 0 (0,0) (1,1) (2,2) (índice de la columna = rowindex + 0)
- slice = 3 z1 = 0 z2 = 1 (0,1) (1,2) (2,3) (índice de la columna = rowindex + 1)
- slice = 4 z1 = 1 z2 = 2 (0,2) (1,3) (índice de la columna = rowindex + 2)
- slice = 5 z1 = 2 z2 = 3 (0,3) (índice de columna = rowindex + 3)
Derivando lo siguiente: j = (m-1) - slice + z2 (con j ++) usando la expresión de la longitud del slice para hacer el criterio de parada: ((m-1) - slice + z2)+(slice -z2 - z1) resulta en: (m-1) - z1 Ahora tenemos los argumentos para el bucle interno: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)
El índice de fila es conocido por j, y de nuevo sabemos que el índice de columna solo comienza a incrementarse cuando j comienza a ser constante, y por lo tanto tener j en la expresión nuevamente no es una mala idea. De las diferencias entre la suma anterior noté que la diferencia siempre es igual a j - (slice - m +1) , probando esto para otros casos. Estaba seguro de que esto sería válido para todos los casos (no soy matemático; P) y, por lo tanto, el algoritmo para el movimiento descendente comenzando desde la parte inferior izquierda se ve de la siguiente manera:
#include <stdio.h>
int main()
{
int x[3][4] = { 1, 2, 3, 4,
5, 6, 7, 8,
9, 10, 11, 12};
int m = 3;
int n = 4;
for (int slice = 0; slice < m + n - 1; ++slice) {
printf("Slice %d: ", slice);
int z1 = slice < n ? 0 : slice - n + 1;
int z2 = slice < m ? 0 : slice - m + 1;
for (int j = (m-1) - slice + z2; j <= (m-1) - z1; j++) {
printf("%d ", x[j][j+(slice-m+1)]);
}
printf("/n");
}
return 0;
}
Ahora les dejo las otras dos direcciones ^^ (que solo es importante cuando la orden es realmente importante).
Este algoritmo es bastante emocionante, incluso cuando piensas que sabes cómo funciona, todavía te puede morder el culo. Sin embargo, creo que es bastante bonito porque literalmente se mueve a través de la matriz como era de esperar. Me interesa saber si alguien sabe más sobre el algoritmo, un nombre por ejemplo, para poder ver si lo que hice aquí realmente tiene sentido y quizás haya mejores soluciones.
La clave es repetir cada elemento en la primera fila, y desde allí bajar la diagonal. Luego, repita cada elemento en la última columna (sin el primero, que cruzamos en el paso anterior) y luego baje por su diagonal.
Aquí está el código fuente que asume que la matriz es una matriz cuadrada (no probada, traducida del código python de trabajo):
#define N 10
void diag_step(int[][] matrix) {
for (int i = 0; i < N; i++) {
int j = 0;
int k = i;
printf("starting a strip/n");
while (j < N && i >= 0) {
printf("%d ", matrix[j][k]);
k--;
j++;
}
printf("/n");
}
for (int i = 1; i < N; i++) {
int j = N-1;
int k = i;
printf("starting a strip/n");
while (j >= 0 && k < N) {
printf("%d ", matrix[k][j]);
k++;
j--;
}
printf("/n");
}
}
Probablemente haga algo así (disculpas de antemano por cualquier error de índice, no lo haya depurado):
// Operation to be performed on each slice:
void doSomething(const int lengthOfSlice,
elementType *slice,
const int stride) {
for (int i=0; i<lengthOfSlice; ++i) {
elementType element = slice[i*stride];
// Operate on element ...
}
}
void operateOnSlices(const int n, elementType *A) {
// distance between consecutive elements of a slice in memory:
const int stride = n - 1;
// Operate on slices that begin with entries in the top row of the matrix
for (int column = 0; column < n; ++column)
doSomething(column + 1, &A[column], stride);
// Operate on slices that begin with entries in the right column of the matrix
for (int row = 1; row < n; ++row)
doSomething(n - row, &A[n*row + (n-1)], stride);
}
Pseudo código:
N = 2 // or whatever the size of the [square] matrix
for x = 0 to N
strip = []
y = 0
repeat
strip.add(Matrix(x,y))
x -= 1
y -= 1
until x < 0
// here to print the strip or do some'' with it
// And yes, Oops, I had missed it...
// the 2nd half of the matrix...
for y = 1 to N // Yes, start at 1 not 0, since main diagonal is done.
strip = []
x = N
repeat
strip.add(Matrix(x,y))
x -= 1
y += 1
until x < 0
// here to print the strip or do some'' with it
(Asume x indexes rows, y indexes columns, invierte estos dos si la matriz está indexada al revés)
Una implementación mucho más fácil:
//Assuming arr as ur array and numRows and numCols as what they say.
int arr[numRows][numCols];
for(int i=0;i<numCols;i++) {
printf("Slice %d:",i);
for(int j=0,k=i; j<numRows && k>=0; j++,k--)
printf("%d/t",arr[j][k]);
}
debe dividir la matriz en partes superior e inferior e iterar cada una de ellas por separado, una media fila primero, otra columna primero. supongamos que la matriz es n * n, almacenada en un vector, fila primero, base cero, los bucles son exclusivos del último elemento.
for i in 0:n
for j in 0:i +1
A[i + j*(n-2)]
the other half can be done in a similar way, starting with:
for j in 1:n
for i in 0:n-j
... each step is i*(n-2) ...
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int N = 0;
cin >> N;
vector<vector<int>> m(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
cin >> m[i][j];
}
}
for (int i = 1; i < N << 1; ++i)
{
for (int j = 0; j < i; ++j)
{
if (j < N && i - j - 1 < N)
{
cout << m[j][i - j - 1];
}
}
cout << endl;
}
return 0;
}
public void printMatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m + n - 1; i++) {
int start_row = i < m ? i : m - 1;
int start_col = i < m ? 0 : i - m + 1;
while (start_row >= 0 && start_col < n) {
System.out.print(matrix[start_row--][start_col++]);
}
System.out.println("/n")
}
}
static int[][] arr = {{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9,10,11,12},
{13,14,15,16} };
public static void main(String[] args) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < i+1; j++) {
System.out.print(arr[j][i-j]);
System.out.print(",");
}
System.out.println();
}
for (int i = 1; i < arr.length; i++) {
for (int j = 0; j < arr.length-i; j++) {
System.out.print(arr[i+j][arr.length-j-1]);
System.out.print(",");
}
System.out.println();
}
}