Traverse Matrix in strisce diagonali

Pensavo che questo problema avesse una soluzione banale, un paio di cicli for e alcuni contatori elaborati, ma a quanto pare è piuttosto più complicato.

Quindi la mia domanda è, come scriveresti (in C) una funzione trasversale di una matrice quadrata in strisce diagonali.

Esempio:

1 2 3 4 5 6 7 8 9 

Dovrebbe essere attraversato nel seguente ordine:

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

Ogni striscia in alto è racchiusa tra parentesi quadre. Uno dei requisiti è riuscire a distinguere tra le strisce. Significa che sai quando stai iniziando una nuova striscia. Questo perché c’è un’altra funzione che devo chiamare per ogni elemento in una striscia e quindi prima dell’inizio di una nuova striscia. Quindi una soluzione senza duplicazione del codice è l’ideale.

    Ecco qualcosa che puoi usare. Basta sostituire la stampa con quello che vuoi veramente fare.

     #include  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; } 

    Produzione:

     Slice 0: 1 Slice 1: 2 4 Slice 2: 3 5 7 Slice 3: 6 8 Slice 4: 9 

    Vorrei spostare le righe in questo modo:

     1 2 3 xx x 4 5 6 x xx 7 8 9 

    E basta scorrere le colonne. Questo può effettivamente essere fatto senza spostamento fisico.

    Diamo un’occhiata a come gli elementi della matrice sono indicizzati.

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

    Ora, diamo un’occhiata alle strisce:

     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) 

    Se osservi da vicino, noterai una cosa. La sum degli indici di ciascun elemento della matrice in ciascuna striscia è costante. Quindi, ecco il codice che fa questo.

     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(); } } 

    Non è l'algoritmo più veloce là fuori (fa (rows * cols * (rows + cols-2)) operazioni), ma la logica dietro è piuttosto semplice.

    Penso che questo possa essere una soluzione per qualsiasi tipo di matrice.

     #include  #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=0 ; --i, ++j) if( (i 

    Pensavo che questo problema avesse una soluzione banale, un paio di cicli for e alcuni contatori fantasiosi

    Precisamente.

    La cosa importante da notare è che se assegni ad ogni elemento un indice ( i , j ) allora gli oggetti sulla stessa diagonale hanno lo stesso valore j + ni , dove n è la larghezza della tua matrice. Quindi, se si esegue un’iterazione sulla matrice nel modo consueto (cioè cicli annidati su i e j ), è ansible tenere traccia delle diagonali in una matrice indirizzata nel modo sopra indicato.

    // Questo algoritmo funziona per matrici di tutte le dimensioni. 😉

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

    Ho trovato questo qui: traversa la matrice rettangular in strisce diagonali

     #include  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; } 

    produzione:

     Slice 0: 1 Slice 1: 5 2 Slice 2: 9 6 3 Slice 3: 10 7 4 Slice 4: 11 8 Slice 5: 12 

    Ho trovato questo un modo abbastanza elegante di farlo in quanto ha solo bisogno di memoria per 2 variabili aggiuntive (z1 e z2), che sostanzialmente contengono le informazioni sulla lunghezza di ogni fetta. Il ciclo esterno si sposta attraverso i numeri di sezione ( slice ) e il ciclo interno passa quindi attraverso ogni sezione con indice: slice - z1 - z2 . Tutte le altre informazioni di cui hai bisogno allora dove inizia l’algoritmo e come si muove attraverso la matrice. Nell’esempio precedente si sposterà dapprima la matrice, e dopo aver raggiunto il fondo si sposterà a destra: (0,0) -> (1,0) -> (2,0) -> (2,1) – > (2,2) -> (2,3). Di nuovo questo modello è catturato dai varibales z1 e z2. La riga incrementa insieme al numero di slice fino a raggiungere il fondo, quindi z2 inizierà ad aumentare che può essere utilizzato per mantenere costante l’indice di riga nella sua posizione: slice - z2 . La lunghezza di ogni slice è nota con: slice - z1 - z2 , perfrimming di quanto segue: (slice - z2) - (slice - z1 -z2) (meno mentre l’algoritmo si muove in ordine ascendente m–, n ++) risulta in z1 che è il criterio di arresto per il ciclo interno. Rimane solo l’indice della colonna che viene convenientemente ereditato dal fatto che j è costante dopo che raggiunge il fondo, dopo di che l’indice della colonna inizia ad aumentare.

    L’algoritmo precedente si muove solo in ordine ascendente da sinistra a destra iniziando in alto a sinistra (0,0). Quando avevo bisogno di questo algoritmo, dovevo anche cercare in una matrice in ordine decrescente iniziando dal basso a sinistra (m, n). Poiché sono stato abbastanza colpito dall’algoritmo, ho deciso di arrivare fino in fondo e adattarlo:

    • la lunghezza della fetta è nuovamente nota con: slice -z1 - z2
    • La posizione iniziale delle fette è: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
    • Il movimento di ogni sezione è m ++ e n ++

    Ho trovato abbastanza utile descriverlo come segue:

    • slice = 0 z1 = 0 z2 = 0 (2,0) (colonna index = rowindex – 2)
    • slice = 1 z1 = 0 z2 = 0 (1,0) (2,1) (colonna index = rowindex – 1)
    • slice = 2 z1 = 0 z2 = 0 (0,0) (1,1) (2,2) (colonna index = rowindex + 0)
    • slice = 3 z1 = 0 z2 = 1 (0,1) (1,2) (2,3) (colonna index = rowindex + 1)
    • slice = 4 z1 = 1 z2 = 2 (0,2) (1,3) (colonna index = rowindex + 2)
    • slice = 5 z1 = 2 z2 = 3 (0,3) (colonna index = rowindex + 3)

    Derivando quanto segue: j = (m-1) - slice + z2 (con j ++) usando l’espressione della lunghezza della slice per definire il criterio di arresto: ((m-1) - slice + z2)+(slice -z2 - z1) risulta in: (m-1) - z1 Ora abbiamo gli argumets per il innerloop: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

    L'indice di riga è noto per j, e ancora sappiamo che l'indice di colonna inizia ad incrementare quando j inizia a essere costante, e quindi avere j nell'espressione di nuovo non è una ctriggers idea. Dalle differenze tra la summenzionata summenzionata ho notato che la differenza è sempre uguale a j - (slice - m +1) , testando questo per altri casi ero sicuro che ciò sarebbe valso per tutti i casi (non sono un matematico; P) e quindi l'algoritmo per il movimento discendente a partire dal basso a sinistra appare come segue:

     #include  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; } 

    Ora lascio le altre due direzioni fino a te ^^ (che è importante solo quando l'ordine è effettivamente importante).

    Questo algoritmo è piuttosto un rompicapo mentale, anche quando pensi di sapere come funziona può ancora morderti nel culo. Comunque penso che sia abbastanza bello perché si muove letteralmente attraverso la matrice come ci si aspetterebbe. Mi interessa sapere se qualcuno ne sa di più dell'algoritmo, un nome per esempio, quindi posso verificare se quello che ho fatto qui ha senso e forse ci sono soluzioni migliori.

    La chiave è di iterare ogni object nella prima riga, e da esso scendere la diagonale. Quindi, iterare ogni elemento nell’ultima colonna (senza il primo, che abbiamo passato nel passaggio precedente) e quindi scendere la sua diagonale.

    Ecco il codice sorgente che presuppone che la matrice sia una matrice quadrata (non testata, tradotta dal codice Python funzionante):

     #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"); } } 

    Pseudo codice:

     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 

    (Presuppone x indicizzare le righe, y indicizzare le colonne, invertire queste due se la matrice è indicizzata al contrario)

    Nel caso qualcuno abbia bisogno di farlo in python, è molto semplice usare numpy:

     #M is a square numpy array for i in range(-M.shape[0]+1, M.shape[0]): print M.diagonal(offset=i) 

    devi spezzare la matrice nelle parti superiore e inferiore, e iterare ciascuna di esse separatamente, una prima riga prima, un’altra prima colonna. supponiamo che la matrice sia n * n, memorizzata in un vettore, riga prima, zero base, i cicli sono esclusivi dell’ultimo 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:nj ... each step is i*(n-2) ... 

    Probabilmente farei qualcosa di simile (mi scuso in anticipo per eventuali errori di indice, non ho eseguito il debug di questo):

     // Operation to be performsd on each slice: void doSomething(const int lengthOfSlice, elementType *slice, const int stride) { for (int i=0; i 
     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][ij]); 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(); } } 

    Un’implementazione molto più semplice:

     //Assuming arr as ur array and numRows and numCols as what they say. int arr[numRows][numCols]; for(int i=0;i=0; j++,k--) printf("%d\t",arr[j][k]); } 
     #include  #include  #include  #include  #include  using namespace std; int main() { int N = 0; cin >> N; vector> m(N, vector(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") } }