Matrice transversale en bandes diagonales

je changerais les lignes comme ceci:

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

et il suffit d'itérer les colonnes. Cela peut être fait sans déplacement physique.

voyons comment les éléments de matrice sont indexés.

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

maintenant, regardons les rayures:

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 vous regardez de plus près, vous remarquerez une chose. La somme des indices de chaque élément de matrice dans chaque bande est constante. Donc, voici le code qui fait cela.

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

Ce n'est pas l'algorithme le plus rapide là-bas (ne(lignes * colonnes * (lignes+colonnes-2))), mais la logique derrière, c'est assez simple.

je pense que cela peut être une solution pour n'importe quel type de matrice.

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

j'ai pensé que ce problème avait une solution triviale, quelques boucles de for et quelques compteurs de fantaisie

précisément.

La chose importante à noter est que si vous donnez à chaque élément d'un index ( je , j ) alors les éléments sur la même diagonale ont la même valeur j + n – je , où n est la largeur de votre matrice. Donc, si vous itérez sur la matrice de la manière habituelle (c.-à-d. boucles imbriquées sur i et j ), alors vous pouvez garder la trace des diagonales dans un tableau qui est adressée de la manière mentionnée ci-dessus.

j'ai trouvé ceci ici: matrice rectangulaire transversale en bandes diagonales

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

sortie:

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

j'ai trouvé cette façon très élégante de le faire car il n'a besoin de mémoire que pour 2 variables supplémentaires (z1 et z2), qui contiennent essentiellement les informations sur la longueur de chaque tranche. La boucle extérieure se déplace à travers les numéros de tranche ( slice ) et la boucle intérieure se déplace ensuite à travers chaque tranche avec indice: slice - z1 - z2 . Toutes les autres informations dont vous avez besoin ensuite où l'algorithme commence et comment il se déplace dans la matrice. Dans l'exemple précédent, il se déplace vers le bas de la matrice en premier, et après qu'il atteigne le bas, il se déplace à droite: (0,0) -> (1,0) -> (2,0) -> (2,1) -> (2,2) -> (2,3). Encore une fois, ce modèle est saisi par les variables z1 et z2. Les incréments de ligne avec le slice nombre jusqu'à ce qu'il atteigne le fond, puis z2 commencera à augmenter qui peut être utilisé pour gardez l'indice de ligne constant à sa position: slice - z2 . Chaque longueur de tranche est connue par: slice - z1 - z2 , perofrming le suivant: (slice - z2) - (slice - z1 -z2) (moins que l'algorithme se déplace dans l'ordre ascendant m--, n++) résultats dans z1 qui est le critère d'arrêt pour la boucle intérieure. Il ne reste que l'index de colonne qui est commodément hérité du fait que j est constant après qu'il atteigne le fond, après quoi l'index de colonne commence à augmenter.

précédant l'algorithme ne se déplace que par ordre ascendant de gauche à droite en commençant par le haut à gauche (0,0). Quand j'avais besoin de cet algorithme,j'avais aussi besoin de chercher dans une matrice dans l'ordre décroissant commençant en bas à gauche (m, n). Parce que j'ai été assez frappé par l'algorithme, j'ai décidé d'aller au fond et de l'adapter:

• longueur de tranche est de nouveau connu par: slice -z1 - z2
• la position de départ des tranches est: (2,0) -> (1,0) -> (0,0) -> (0,1) -> (0,2) -> (0,3)
• le mouvement de chaque tranche est m++ et n++

j'ai trouvé très utile de le décrire comme suit:

• tranche=0 z1=0 z2=0 (2,0) (indice de la colonne= rowindex - 2)
• tranche=1 z1=0 i2=0 (1,0) (2,1) (index de colonne= rowindex - 1)
• tranche=2 z1=0 z2=0 (0,0) (1,1) (2,2) (colonne index = rowindex + 0)
• tranche=3 z1=0 z2=1 (0,1) (1,2) (2,3) (colonne index = rowindex + 1)
• tranche=4 z1=1 z2=2 (0,2) (1,3) (indice de la colonne= rowindex + 2)
• tranche=5 z1=2 z2=3 (0,3) (indice de la colonne= rowindex + 3)

dérivant le suivant: j = (m-1) - slice + z2 (avec j++) en utilisant l'expression de la longueur de la tranche pour rendre le critère d'arrêt: ((m-1) - slice + z2)+(slice -z2 - z1) se traduit par: (m-1) - z1 Nous avons maintenant les argumets pour l'intérieur.: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

L'index de ligne est de savoir par j, et encore, nous savons que l'index de colonne commence seulement incrémentation quand j commence à être constant, et donc j dans l'expression n'est pas une mauvaise idée. D'après les différences entre les sommations ci-dessus, j'ai remarqué que la différence est toujours égale à j - (slice - m +1) , ce test pour certains autres cas, j'étais sûr que cela tiendrait pour tous les cas (je ne suis pas un mathématicien ;P) et donc l'algorithme pour la décroissance mouvement à partir du bas à gauche ressemble comme suit:

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

Maintenant, je laisse les deux autres directions jusqu'à vous ^^ (ce qui est important quand l'ordre est important).

cet algorithme est un sacré casse-tête, même si vous pensez savoir comment il fonctionne, il peut encore vous mordre le cul. Cependant, je pense qu'il est assez beau parce qu'il se déplace littéralement à travers la matrice comme vous l'attendez. Je suis intéressé si quelqu'un sait en savoir plus sur l'algorithme, un nom par exemple, donc je peux regarder si ce que j'ai fait ici a réellement un sens et peut-être Il ya une meilleure solutions.

// Cet algorithme fonctionne pour les matrices de toutes tailles. ;)

    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;

        }

    }

la clé est d'itérer chaque élément dans la première rangée, et de lui descendre la diagonale. Ensuite, itérez chaque élément de la dernière colonne (sans le premier, que nous avons traversé à l'étape précédente) et descendez sa diagonale.

voici le code source qui suppose que la matrice est une matrice carrée (non testée, traduite à partir du code Python):

#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 code:

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

(ce qui Suppose que x indices de lignes, y index des colonnes, à l'inverse de ces deux si la matrice est indexé dans l'autre sens)

juste au cas où quelqu'un aurait besoin de faire cela en python, c'est très facile d'utiliser numpy:

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

vous devez briser la matrice dans les parties supérieures et inférieures, et itérer chacun d'eux séparément, une demi-rangée d'abord, une autre colonne d'abord. supposons que la matrice est n*n, stockée dans un vecteur, rangée d'abord, base zéro, les boucles sont exclusives au dernier élément.

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

je ferais probablement quelque chose comme ceci (excuses à l'avance pour toute erreur d'index, n'ont pas débogué ceci):

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

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

beaucoup plus de facilité de mise en œuvre:

//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]);
}

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