7

この質問はこれに似ていますが、正方形を表す配列の代わりに、長方形の配列を転置する必要があります。

したがって、幅：xと高さ：yが与えられた場合、私の配列にはx*y要素があります。

幅が4、高さが3の場合、次のようになります。

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

これは行列を表します：

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

をお願いします：

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

私は新しい配列を作成することによってそれを行う方法を知っていますが、前述の質問の解決策のようにその場でそれを行う方法を知りたいです。

4

2 に答える 2

3

所定の位置に転置する簡単な方法は、マトリックスの背面から開始して各要素を所定の位置に回転させることです。一度に1つの要素を所定の位置に回転させるだけでよいので、たとえば、で始まると[0,1,2,3,4,5,6,7,8,9,a,b]、次のようになります。

0,1,2,3,4,5,6,7,8,9,a,b, // step 0
                     ,b, // step 1
             ,8,9,a,7,   // step 2
      4,5,6,8,9,a,3,     // step 3
               ,a,       // step 4
         ,8,9,6,         // step 5
   ,4,5,8,9,2,           // step 6
         ,9,             // step 7
     ,8,5,               // step 8
 ,4,8,1,                 // step 9
   ,8,                   // step 10
 ,4,                     // step 11
0,                       // step 12

（これは、各ステップで要素が最終位置に回転したことを示しています。）

各要素に対して（後ろから前に）回転する要素の数を書き出すと、それは素晴らしい進行を形成します。例（width= 4、height= 3）の場合：

1,4,7,1,3,5,1,2,3,1,1,1

または、少し構造化された方法で：

1,4,7,
1,3,5,
1,2,3,
1,1,1

1つの要素のローテーションは事実上何も実行されませんが、進行は非常に単純なアルゴリズム（C ++）につながります。

void transpose(int *matrix, int width, int height)
{
    int count= width*height;

    for (int x= 0; x<width; ++x)
    {
        int count_adjustment= width - x - 1;

        for (int y= 0, step= 1; y<height; ++y, step+= count_adjustment)
        {
            int last= count - (y+x*height);
            int first= last - step;

            std::rotate(matrix + first, matrix + first + 1, matrix + last);
        }
    }
}
于 2012-01-04T20:41:08.267 に答える
2

これを行う1つの方法は、元のマトリックスの既存の各要素を新しい位置に移動することです。最初に宛先インデックスの値を取得するように注意して、新しい位置にも移動できるようにします。任意のNxM行列の場合、インデックスXの要素の宛先インデックスは次のように計算できます。

X_new = ((N*X) / (M*N)) + ((N*X) % (M*N))

ここで、「/」演算子は整数の除算（商）を表し、「％」はモジュロ演算子（余り）を表します。ここではPython構文を使用しています。

問題は、任意の場所から開始した場合、マトリックス内のすべての要素をトラバースすることが保証されていないことです。これを回避する最も簡単な方法は、正しい位置に移動された要素のビットマップを維持することです。

これを実現するPythonコードは次のとおりです。

M = 4
N = 3
MN = M*N

X = range(0,MN)

bitmap = (1<<0) + (1<<(MN-1))
i = 0

while bitmap != ( (1<<MN) - 1):
    if (bitmap & (1<<i)):
        i += 1
        xin = X[i]
        i = ((N*i)/MN) + ((N*i) % MN)
    else:
        xout = X[i]
        X[i] = xin
        bitmap += (1<<i)
        i = ((N*i)/MN) + ((N*i) % MN)
        xin = xout

print X

ここでは、わかりやすくするためにいくつかの最適化を犠牲にしました。より複雑なアルゴリズムを使用してビットマップを回避することも可能です。計算を犠牲にしてメモリを節約することに真剣に取り組んでいる場合は、関連するWikipediaの記事の参照を参照してください。

于 2012-01-04T20:59:14.943 に答える