c - 抽出 - 対角行列 交換可能



対角線のトラバース行列 (11)

私はこの問題には些細な解決策があると思っていました。

正確に。

注意すべき重要な点は、各アイテムにインデックス( ij )を付けると、同じ対角線上のアイテムは同じ値j + n - iを持ちます。ここで、 nはマトリックスの幅です。 したがって、通常の方法(つまり、 ijの入れ子になったループ)で行列を繰り返し処理すれば、上の方法で扱われる配列の対角線を追跡できます。

私は、この問題には些細な解決策、ループ用のカップル、ファンキーなカウンターがいくつかあると思いましたが、明らかに複雑です。

だから私の質問は、(Cで)正方行列の対角線の関数のトラバーサルを書く方法は?

例:

1  2  3
4  5  6
7  8  9

次の順序でトラバースする必要があります:

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

上の各ストリップは大括弧で囲まれています。 要件の1つは、ストリップを区別できることです。 あなたが新しいストリップを始めるときにあなたが知っている意味。 これは、ストリップ内の各アイテムに対して、次に新しいストリップの開始前に呼び出さなければならない別の機能があるためです。 したがって、コードの重複のないソリューションが理想的です。


//このアルゴリズムはすべてのサイズの行列に対して機能します。 ;)

    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;

        }

    }

はるかに簡単な実装:

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

キーは、最初の行のすべてのアイテムを反復することです、そして、それから斜めに下がります。 次に、最後の列のすべての項目を反復して(前の手順で最初に実行したものを除いて)、次に対角を下ろします。

ここでは、行列が正方行列(テストされていない、動作中の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");
    }   
}   

擬似コード:

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

(xインデックスの行、yインデックスの列、行列がインデックスされていればこれらの2つを逆にする)


私はおそらくこのような何かをするだろう(インデックスエラーのために事前にお詫びし、これをデバッグしていない):

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

私はこれをここで見つけました: 対角線ストリップのトラバース矩形マトリックス

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

出力:

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

これは基本的に各スライスの長さに関する情報を保持する2つの追加変数(z1とz2)のメモリだけを必要とするので、これを行うには非常にエレガントな方法です。 外側のループはスライス番号( slice )を移動し、内側のループはindex: slice - z1 - z2各スライスを移動します。 その他の情報は、アルゴリズムが開始される場所と、行列がどのように移動するのかに必要な情報です。 上の例では、最初に行列を下に移動し、下に達すると右に移動します:(0,0)→(1,0)→(2,0)→(2,1) - >(2,2) - >(2,3)である。 再び、このパターンはバリバリz1およびz2によって捕捉される。 行がslice番号とともにインクリメントされ、 slice番号が下に達するとz2がインクリメントを開始し、行インデックスをslice - z2の位置に一定に保ちslice - z2 。 各スライスの長さは、 slice - z1 - z2によってわかります。 (slice - z2) - (slice - z1 -z2) (アルゴリズムが昇順に移動すると、マイナス、n ++)はz1になります。内部ループの停止基準。 jが底に達した後は一定であるという事実から便利に継承される列インデックスのみが残っており、その後に列インデックスが増加し始める。

先行アルゴリズムは、左上(0,0)から左から右へ昇順に移動します。 このアルゴリズムが必要なときは、左下(m、n)から順に降順で検索する必要がありました。 私はアルゴリズムによってかなり打たれたので、私は一番下に着いてそれに適応することに決めました:

  • スライスの長さは、 slice -z1 - z2
  • スライスの開始位置は、(2,0)→(1,0)→(0,0)→(0,1)→(0,2)→(0,3)
  • 各スライスの動きはm ++とn ++です

私はそれを次のように描写することが非常に有用であることを発見しました:

  • スライス= 0 z1 = 0 z2 = 0(2,0)(列インデックス=行インデックス-2)
  • スライス= 1 z1 = 0 z2 = 0(1,0)(2,1)(列インデックス=行インデックス-1)
  • スライス= 2 z1 = 0 z2 = 0(0,0)(1,1)(2,2)(列インデックス=行インデックス+0)
  • スライス= 3 z1 = 0 z2 = 1(0,1)(1,2)(2,3)(列インデックス=行インデックス+1)
  • スライス= 4z1 = 1z2 = 2(0,2)(1,3)(列インデックス=行インデックス+2)
  • スライス= 5z1 = 2z2 = 3(0,3)(列インデックス=行インデックス+3)

((m-1) - slice + z2)+(slice -z2 - z1)スライス長の式を用いて、 j = (m-1) - slice + z2 (j ++で) ((m-1) - slice + z2)+(slice -z2 - z1)ます。 (m-1) - z1ここで、intloopの引数は次のようになります: for (int j = (m-1) - slice + z2; j < (m-1) - z1; j++)

行インデックスはjによって認識されています。また、jが定数になるときに列インデックスがインクリメントを開始することがわかります。したがって、式の中に再びjを入れることは悪い考えではありません。 上記の総和の差から、私は差が常にj - (slice - m +1)に等しいことに気付きました。これを他のいくつかのケースでテストしましたが、これはすべてのケースで成立すると確信していました(私は数学者ではありません。 P)であり、したがって、左下から始まる降順移動のアルゴリズムは以下のようになる。

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

今、私は他の2つの方向をあなたに任せます^^(注文が実際に重要な場合にのみ重要です)。

このアルゴリズムは、たとえそれがどのように動作するかを知っていると思っても、あなたのお尻にあなたを噛ませることができます。 しかし、それは文字通りあなたが期待しているように行列を動くので、それはかなり美しいと思います。 もし私がここでやったことが実際に意味を成しているのか、もっと良い解決策があるのか​​を誰かが知っていれば興味があります。


私は次のように行をシフトします:

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

そして列を反復するだけです。 これは実際に物理的なシフトなしで行うことができます。


誰かがPythonでこれを行う必要がある場合に備えて、numpyを使うのはとても簡単です:

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

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

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