二次元配列を回転するにはどうすればよいでしょうか?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
に触発された レイモンド・チェンの投稿, 4x4 の 2 次元配列があるとします。それを 90 度回転する関数を作成します。Raymond は疑似コードでソリューションにリンクしていますが、実際の世界のものを見てみたいと思います。
[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]
次のようになります:
[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]
アップデート:Nick の答えは最も簡単ですが、n^2 よりも優れた方法はありますか?マトリックスが 10000x10000 だったらどうなるでしょうか?
解決
こちらがC#です
int[,] array = new int[4,4] {
{ 1,2,3,4 },
{ 5,6,7,8 },
{ 9,0,1,2 },
{ 3,4,5,6 }
};
int[,] rotated = RotateMatrix(array, 4);
static int[,] RotateMatrix(int[,] matrix, int n) {
int[,] ret = new int[n, n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
ret[i, j] = matrix[n - j - 1, i];
}
}
return ret;
}
他のヒント
O(n^2) 時間および O(1) 空間アルゴリズム （回避策や気の利いたことは一切なし！)
+90 回転:
- 転置
- 各行を反転します
-90 度回転:
方法 1 :
- 転置
- 各列を反転します
方法 2 :
- 各行を反転します
- 転置
+180 回転:
方法 1:+90回転を2回
方法 2:各行を反転し、次に各列を反転します (転置)
-180 回転:
方法 1:-90度回転を2回
方法 2:各列を反転し、次に各行を反転します
方法 3:同じなので+180回転
もう少し詳細を追加したいと思います。この回答では、重要な概念が繰り返され、ペースが遅く、意図的に繰り返しられています。ここで提供される解決策は、構文的に最もコンパクトではありませんが、行列の回転とは何か、およびその結果の実装を学びたい人を対象としています。
まず、マトリックスとは何でしょうか?この回答の目的では、行列は幅と高さが同じ単なるグリッドです。行列の幅と高さは異なっていてもよいことに注意してください。ただし、簡単にするために、このチュートリアルでは幅と高さが等しい行列のみを考慮します (正方行列）。はい、 行列 マトリックスの複数形です。
行列の例は次のとおりです。2×2、3×3、または5×5。または、より一般的には N×N。2×2=4 であるため、2×2 行列には 4 つの正方形があります。5×5 = 25 であるため、5×5 行列には 25 個の正方形があります。各四角形は要素またはエントリと呼ばれます。各要素をピリオドで表します (.) 以下の図では次のようになります。
2×2マトリックス
. .
. .
3×3マトリックス
. . .
. . .
. . .
4×4マトリックス
. . . .
. . . .
. . . .
. . . .
では、行列を回転するとはどういう意味でしょうか?2×2 行列をとり、回転を観察できるように各要素にいくつかの数値を入れてみましょう。
0 1
2 3
これを 90 度回転すると、次のようになります。
2 0
3 1
車のハンドルを回すのと同じように、文字通りマトリックス全体を右に 1 回回転させました。マトリックスを右側に「傾ける」ことを考えると役立つかもしれません。行列を取得して右に 1 回回転する関数を Python で作成したいと考えています。関数のシグネチャは次のようになります。
def rotate(matrix):
# Algorithm goes here.
行列は 2 次元配列を使用して定義されます。
matrix = [
[0,1],
[2,3]
]
したがって、最初のインデックス位置が行にアクセスします。2 番目のインデックス位置は列にアクセスします。
matrix[row][column]
行列を出力するユーティリティ関数を定義します。
def print_matrix(matrix):
for row in matrix:
print row
マトリックスを回転する 1 つの方法は、一度にレイヤーごとに回転することです。しかし、レイヤーとは何でしょうか?タマネギを思い浮かべてください。タマネギの層のように、各層が取り除かれるにつれて、中心に向かって移動します。他の例え話としては、 マトリョーシカ人形 または小包を渡すゲーム。
マトリックスの幅と高さによって、そのマトリックスのレイヤー数が決まります。各レイヤーに異なるシンボルを使用してみましょう。
2×2 マトリックスには 1 つのレイヤーがあります
. .
. .
3×3 マトリックスには 2 つの層があります
. . .
. x .
. . .
4×4 マトリックスには 2 つの層があります
. . . .
. x x .
. x x .
. . . .
5×5のマトリックスには3つの層があります
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
6×6 マトリックスには 3 つの層があります
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
7×7 マトリックスには 4 つの層があります
. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .
マトリックスの幅と高さを 1 ずつ増やしても、必ずしもレイヤーの数が増えるわけではないことに気づくかもしれません。上記の行列を取得してレイヤーと寸法を表にすると、幅と高さが 2 増加するごとにレイヤーの数が 1 回増加することがわかります。
+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 | 1 |
| 2×2 | 1 |
| 3×3 | 2 |
| 4×4 | 2 |
| 5×5 | 3 |
| 6×6 | 3 |
| 7×7 | 4 |
+-----+--------+
ただし、すべてのレイヤーを回転する必要があるわけではありません。1×1 行列は回転前でも回転後でも同じです。中央の 1×1 レイヤーは、マトリックス全体がどれほど大きくても、回転の前後で常に同じです。
+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 | 1 | 0 |
| 2×2 | 1 | 1 |
| 3×3 | 2 | 1 |
| 4×4 | 2 | 2 |
| 5×5 | 3 | 2 |
| 6×6 | 3 | 3 |
| 7×7 | 4 | 3 |
+-----+--------+------------------+
N×N 行列が与えられた場合、回転する必要があるレイヤーの数をプログラムでどのように決定できるでしょうか?幅または高さを 2 で割って余りを無視すると、次の結果が得られます。
+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers | N/2 |
+-----+--------+------------------+---------+
| 1×1 | 1 | 0 | 1/2 = 0 |
| 2×2 | 1 | 1 | 2/2 = 1 |
| 3×3 | 2 | 1 | 3/2 = 1 |
| 4×4 | 2 | 2 | 4/2 = 2 |
| 5×5 | 3 | 2 | 5/2 = 2 |
| 6×6 | 3 | 3 | 6/2 = 3 |
| 7×7 | 4 | 3 | 7/2 = 3 |
+-----+--------+------------------+---------+
方法に注目してください N/2 回転する必要があるレイヤーの数は一致しますか?場合によっては、回転可能なレイヤーの数が、マトリックスのレイヤーの総数から 1 つ減ったものになることがあります。これは、最内層が 1 つの要素のみで構成されている場合に発生します (つまり、1×1 行列）なので、回転する必要はありません。それは単に無視されるだけです。
行列を回転するには関数内でこの情報が間違いなく必要になるため、今すぐ追加しましょう。
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
これで、レイヤーが何であるか、実際に回転する必要があるレイヤーの数を決定する方法がわかりました。回転できるように単一のレイヤーを分離するにはどうすればよいでしょうか?まず、マトリックスを最外層から内部に向かって最内層まで検査します。5×5 マトリックスには合計 3 つのレイヤーと、回転が必要な 2 つのレイヤーがあります。
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
まずはコラムを見てみましょう。最外層を定義する列の位置は、0 から数えると仮定すると、0 と 4 になります。
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
0 と 4 は最外層の行の位置でもあります。
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
幅と高さは同じなので、これは常に当てはまります。したがって、レイヤーの列と行の位置を (4 つではなく) 2 つの値だけで定義できます。
内側の 2 番目のレイヤーに移動すると、列の位置は 1 と 3 になります。そして、はい、ご想像のとおり、行についても同じです。次のレイヤーに向かって内側に移動するときは、行と列の位置を増減する必要があることを理解することが重要です。
+-----------+---------+---------+---------+
| Layer | Rows | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes |
| Inner | 1 and 3 | 1 and 3 | Yes |
| Innermost | 2 | 2 | No |
+-----------+---------+---------+---------+
したがって、各層を検査するには、最も外側の層から開始して内側への移動を表す、増加するカウンターと減少するカウンターの両方を含むループが必要です。これを「レイヤーループ」と呼びます。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
print 'Layer %d: first: %d, last: %d' % (layer, first, last)
# 5x5 matrix
matrix = [
[ 0, 1, 2, 3, 4],
[ 5, 6, 6, 8, 9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate(matrix)
上記のコードは、回転する必要があるレイヤーの (行と列) 位置をループします。
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
これで、各レイヤーの行と列の位置を提供するループができました。変数 first そして last 最初と最後の行と列のインデックス位置を識別します。行と列のテーブルに戻ります。
+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
| | . . . . . |
| | . x x x . |
| | . x O x . |
| | . x x x . |
| | . . . . . |
+--------+-----------+
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
したがって、マトリックスのレイヤー間を移動できます。次に、レイヤー内で要素を移動できるようにレイヤー内を移動する方法が必要です。要素はあるレイヤーから別のレイヤーに「ジャンプ」することはありませんが、それぞれのレイヤー内で移動することに注意してください。
レイヤー内の各要素を回転すると、レイヤー全体が回転します。マトリックス内のすべてのレイヤーを回転すると、マトリックス全体が回転します。この文は非常に重要なので、次に進む前に理解するように努めてください。
ここで、要素を実際に移動する方法が必要です。各要素を回転させ、続いてレイヤーを回転させ、最終的にはマトリックスを回転させます。簡単にするために、回転可能なレイヤーが 1 つある 3x3 マトリックスに戻します。
0 1 2
3 4 5
6 7 8
レイヤー ループは、最初と最後の列、および最初と最後の行のインデックスを提供します。
+-----+-------+
| Col | 0 1 2 |
+-----+-------+
| | 0 1 2 |
| | 3 4 5 |
| | 6 7 8 |
+-----+-------+
+-----+-------+
| Row | |
+-----+-------+
| 0 | 0 1 2 |
| 1 | 3 4 5 |
| 2 | 6 7 8 |
+-----+-------+
行列は常に正方行列なので、必要な変数は 2 つだけです。 first そして last, インデックスの位置は行と列で同じであるためです。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Our layer loop i=0, i=1, i=2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# We want to move within a layer here.
変数 first と last は、行列の 4 隅を参照するために簡単に使用できます。これは、コーナー自体がさまざまな順列を使用して定義できるためです。 first そして last (これらの変数の減算、加算、またはオフセットなし):
+---------------+-------------------+-------------+
| Corner | Position | 3x3 Values |
+---------------+-------------------+-------------+
| top left | (first, first) | (0,0) |
| top right | (first, last) | (0,2) |
| bottom right | (last, last) | (2,2) |
| bottom left | (last, first) | (2,0) |
+---------------+-------------------+-------------+
このため、外側の 4 つの角から回転を開始します。最初にそれらを回転させます。それらを強調表示しましょう *.
* 1 *
3 4 5
* 7 *
それぞれ交換したいです * とともに * その右側にあります。それでは、さまざまな順列のみを使用して定義されたコーナーを印刷してみましょう。 first そして last:
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = (first, first)
top_right = (first, last)
bottom_right = (last, last)
bottom_left = (last, first)
print 'top_left: %s' % (top_left)
print 'top_right: %s' % (top_right)
print 'bottom_right: %s' % (bottom_right)
print 'bottom_left: %s' % (bottom_left)
matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]
rotate(matrix)
出力は次のようになります。
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
これで、レイヤー ループ内から各コーナーを非常に簡単に交換できるようになりました。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
top_left = matrix[first][first]
top_right = matrix[first][last]
bottom_right = matrix[last][last]
bottom_left = matrix[last][first]
# bottom_left -> top_left
matrix[first][first] = bottom_left
# top_left -> top_right
matrix[first][last] = top_left
# top_right -> bottom_right
matrix[last][last] = top_right
# bottom_right -> bottom_left
matrix[last][first] = bottom_right
print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)
コーナーを回転する前の行列:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
コーナーを回転した後の行列:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
素晴らしい！マトリックスの各隅を正常に回転できました。ただし、各レイヤーの中央の要素は回転していません。明らかに、レイヤー内で反復する方法が必要です。
問題は、これまでの関数内の唯一のループ (レイヤー ループ) が、反復ごとに次のレイヤーに移動することです。マトリックスには回転可能なレイヤーが 1 つしかないため、レイヤー ループはコーナーのみを回転した後に終了します。より大きな 5×5 マトリックス (2 つのレイヤーを回転する必要がある場合) で何が起こるかを見てみましょう。関数コードは省略されていますが、上記と同じです。
matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)
出力は次のとおりです。
[20, 1, 2, 3, 0]
[ 5, 16, 7, 6, 9]
[10, 11, 12, 13, 14]
[15, 18, 17, 8, 19]
[24, 21, 22, 23, 4]
最外層の角が回転しているのは驚くべきことではありませんが、次の層 (内側) の角も回転していることに気づくかもしれません。意味あり。レイヤー間を移動し、各レイヤーの角を回転するコードを作成しました。これは進歩のように感じますが、残念ながら一歩後退する必要があります。前の (外側) レイヤーが完全に回転するまで、次のレイヤーに移ることはできません。つまり、レイヤー内の各要素が回転されるまでです。角だけを回転させるだけではダメ！
深呼吸する。別のループが必要です。ネストされたループも同様です。新しいネストされたループは、 first そして last 変数に加えて、レイヤー内を移動するためのオフセットも含まれます。この新しいループを「要素ループ」と呼びます。要素ループは、上の行に沿って各要素を訪問し、右側の各要素を訪問し、下の行に沿って各要素を訪問し、左側の上の各要素を訪問します。
- 一番上の行に沿って前方に移動するには、列インデックスをインクリメントする必要があります。
- 右側を下るには、行インデックスを増分する必要があります。
- 底部に沿って後方に移動するには、列インデックスを減らす必要があります。
- 左側に移動するには、行インデックスを減らす必要があります。
これは複雑に思えますが、上記の目的を達成するために増加および減少する回数は行列の 4 辺すべてで同じままであるため、簡単になります。例えば：
- 上の行に 1 つの要素を移動します。
- 1 要素を右側に移動します。
- 一番下の行に沿って 1 要素を後方に移動します。
- 1 要素を左側の上に移動します。
これは、単一の変数を組み合わせて使用できることを意味します。 first そして last レイヤー内で移動する変数。上の行を移動する場合と右側を下に移動する場合はどちらも増分する必要があることに注意してください。下部に沿って後方に移動するときと、左側を上部に移動するときは両方とも減少する必要があります。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
# Move through layers (i.e. layer loop).
for layer in range(0, layer_count):
first = layer
last = size - first - 1
# Move within a single layer (i.e. element loop).
for element in range(first, last):
offset = element - first
# 'element' increments column (across right)
top_element = (first, element)
# 'element' increments row (move down)
right_side = (element, last)
# 'last-offset' decrements column (across left)
bottom = (last, last-offset)
# 'last-offset' decrements row (move up)
left_side = (last-offset, first)
print 'top: %s' % (top)
print 'right_side: %s' % (right_side)
print 'bottom: %s' % (bottom)
print 'left_side: %s' % (left_side)
ここで、上を右側に、右側を下に、下を左側に、左側を上に割り当てるだけです。これをすべてまとめると次のようになります。
def rotate(matrix):
size = len(matrix)
layer_count = size / 2
for layer in range(0, layer_count):
first = layer
last = size - first - 1
for element in range(first, last):
offset = element - first
top = matrix[first][element]
right_side = matrix[element][last]
bottom = matrix[last][last-offset]
left_side = matrix[last-offset][first]
matrix[first][element] = left_side
matrix[element][last] = top
matrix[last][last-offset] = right_side
matrix[last-offset][first] = bottom
マトリックスを考えると:
0, 1, 2
3, 4, 5
6, 7, 8
私たちの rotate 関数の結果は次のようになります。
6, 3, 0
7, 4, 1
8, 5, 2
パイソン:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
安いですね、分かります。
そして反時計回りに:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
これがどのように機能するか: (コメントでリクエスト)
zip(*original) リストの対応する項目を新しいリストにスタックすることにより、2D 配列の軸を交換します。( * 演算子は、含まれているリストを引数に分配するように関数に指示します)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
の [::-1] ステートメントは配列要素を反転します (「 拡張スライス).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
最後に、この 2 つを組み合わせると回転変換が行われます。
の配置の変更 [::-1] マトリックスのさまざまなレベルでリストを反転します。
これは、結果を保持するために完全に新しい配列を使用するのではなく、その場で回転を行うものです。配列の初期化と出力は省略しました。これは正方配列にのみ機能しますが、任意のサイズにすることができます。メモリのオーバーヘッドは配列の 1 つの要素のサイズに等しいため、必要なだけ大きな配列を回転できます。
int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
for (int j = i; j < n - i - 1; j++)
{
tmp = a[i][j];
a[i][j] = a[j][n-i-1];
a[j][n-i-1] = a[n-i-1][n-j-1];
a[n-i-1][n-j-1] = a[n-j-1][i];
a[n-j-1][i] = tmp;
}
}
ここには優れたコードがたくさんありますが、コードのロジックをもう少しよく理解できるように、何が起こっているのかを幾何学的に示したいだけです。これに私がどのようにアプローチするかは次のとおりです。
まず第一に、これを非常に簡単な移調と混同しないでください。
基本的な考え方は、それをレイヤーとして扱い、一度に 1 つのレイヤーを回転させることです。
四輪駆動車があるとします
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
時計回りに 90 度回転すると、次のようになります。
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
これを分解しましょう。まず基本的に 4 つの角を回転します。
1 4
13 16
次に、斜めになっている次のダイヤモンドを回転させます。
2
8
9
15
そして2番目の斜めのダイヤモンド
3
5
12
14
これで外側のエッジが処理されるので、基本的には一度に 1 つのシェルを実行して、
最後に中央の正方形（または奇数の場合は移動しない最後の要素のみ）
6 7
10 11
それでは、各層のインデックスを計算しましょう。常に最外層を操作していると仮定して、次のことを行っています。
[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]
私たちが端の途中になるまで
一般的にパターンは次のとおりです
[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
前回の投稿で述べたように、任意のサイズの行列に対して O(1) 行列回転を実装する C# のコードを次に示します。簡潔さと読みやすさを考慮して、エラー チェックや範囲チェックは行っていません。コード：
static void Main (string [] args)
{
int [,]
// create an arbitrary matrix
m = {{0, 1}, {2, 3}, {4, 5}};
Matrix
// create wrappers for the data
m1 = new Matrix (m),
m2 = new Matrix (m),
m3 = new Matrix (m);
// rotate the matricies in various ways - all are O(1)
m1.RotateClockwise90 ();
m2.Rotate180 ();
m3.RotateAnitclockwise90 ();
// output the result of transforms
System.Diagnostics.Trace.WriteLine (m1.ToString ());
System.Diagnostics.Trace.WriteLine (m2.ToString ());
System.Diagnostics.Trace.WriteLine (m3.ToString ());
}
class Matrix
{
enum Rotation
{
None,
Clockwise90,
Clockwise180,
Clockwise270
}
public Matrix (int [,] matrix)
{
m_matrix = matrix;
m_rotation = Rotation.None;
}
// the transformation routines
public void RotateClockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
}
public void Rotate180 ()
{
m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
}
public void RotateAnitclockwise90 ()
{
m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
}
// accessor property to make class look like a two dimensional array
public int this [int row, int column]
{
get
{
int
value = 0;
switch (m_rotation)
{
case Rotation.None:
value = m_matrix [row, column];
break;
case Rotation.Clockwise90:
value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
break;
case Rotation.Clockwise180:
value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
break;
case Rotation.Clockwise270:
value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
break;
}
return value;
}
set
{
switch (m_rotation)
{
case Rotation.None:
m_matrix [row, column] = value;
break;
case Rotation.Clockwise90:
m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
break;
case Rotation.Clockwise180:
m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
break;
case Rotation.Clockwise270:
m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
break;
}
}
}
// creates a string with the matrix values
public override string ToString ()
{
int
num_rows = 0,
num_columns = 0;
switch (m_rotation)
{
case Rotation.None:
case Rotation.Clockwise180:
num_rows = m_matrix.GetUpperBound (0);
num_columns = m_matrix.GetUpperBound (1);
break;
case Rotation.Clockwise90:
case Rotation.Clockwise270:
num_rows = m_matrix.GetUpperBound (1);
num_columns = m_matrix.GetUpperBound (0);
break;
}
StringBuilder
output = new StringBuilder ();
output.Append ("{");
for (int row = 0 ; row <= num_rows ; ++row)
{
if (row != 0)
{
output.Append (", ");
}
output.Append ("{");
for (int column = 0 ; column <= num_columns ; ++column)
{
if (column != 0)
{
output.Append (", ");
}
output.Append (this [row, column].ToString ());
}
output.Append ("}");
}
output.Append ("}");
return output.ToString ();
}
int [,]
// the original matrix
m_matrix;
Rotation
// the current view of the matrix
m_rotation;
}
OK、手を挙げます。回転時に元の配列は実際には変更されません。ただし、オブジェクト指向システムでは、オブジェクトがクラスのクライアントに対して回転されているように見える限り、問題はありません。現時点では、Matrix クラスは元の配列データへの参照を使用するため、m1 の値を変更すると m2 と m3 も変更されます。コンストラクターを少し変更して、新しい配列を作成し、そこに値をコピーすると、これが解決されます。
(おそらく物理的に保存された表現を更新するために) データを所定の位置で回転することが必要になる場合がありますが、配列アクセスに間接層 (おそらくインターフェイス) を追加すると、より簡単になり、パフォーマンスも向上する可能性があります。
interface IReadableMatrix
{
int GetValue(int x, int y);
}
もしあなたの Matrix すでにこのインターフェースを実装している場合は、 デコレーター このようなクラス:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
+90/-90/180 度の回転、水平/垂直の反転、スケーリングもすべてこの方法で実現できます。
パフォーマンスは特定のシナリオで測定する必要があります。ただし、O(n^2) 操作は O(1) 呼び出しに置き換えられました。これは仮想メソッド呼び出しです。 は 配列への直接アクセスよりも遅いため、回転後に回転された配列が使用される頻度によって異なります。一度使えば間違いなくこのアプローチが勝つでしょう。ローテーションしてから長時間実行するシステムで数日間使用する場合は、インプレースローテーションの方がパフォーマンスが向上する可能性があります。また、初期費用を受け入れることができるかどうかも異なります。
すべてのパフォーマンスの問題と同様に、測定、測定、測定!
これは Java での改良版です。幅と高さが異なる行列用に作成しました
- h は回転後の行列の高さです。
- w は回転後の行列の幅です。
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
このコードは Nick Berardi の投稿に基づいています。
Ruby の方法: .transpose.map &:reverse
すでに多くの回答があり、O(1) 時間の計算量を主張する回答が 2 つ見つかりました。の 本物 O(1) アルゴリズムでは、配列ストレージはそのままにし、その要素のインデックス付け方法を変更します。ここでの目標は、追加のメモリを消費せず、データの反復に追加の時間を必要としないことです。
90、-90、および 180 度の回転は、2D 配列に行と列の数がわかっていれば実行できる単純な変換です。ベクトルを 90 度回転するには、軸を交換して Y 軸を無効にします。-90 度の場合は、軸を交換し、X 軸を無効にします。180 度の場合は、交換せずに両方の軸を無効にします。
軸を個別に無効にすることで水平および/または垂直にミラーリングするなど、さらなる変換も可能です。
これは、例えば次のように行うことができます。アクセサメソッド。以下の例は JavaScript 関数ですが、概念はすべての言語に同様に適用されます。
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);このコードは、内部の各配列が行である、入れ子になった配列の配列を想定しています。
このメソッドを使用すると、配列が回転または変換されたかのように、要素を (ランダムな順序であっても) 読み取る (または書き込む) ことができます。ここで、おそらく参照によって、呼び出す適切な関数を選択するだけで完了です。
この概念は、アクセサー メソッドを通じて追加的に (非破壊的に) 変換を適用するように拡張できます。任意の角度の回転とスケーリングを含みます。
すでに何人かの人が、新しい配列の作成を含む例を提出しています。
他に考慮すべき点がいくつかあります。
(a) 実際にデータを移動する代わりに、単に「回転された」配列を別の方法で走査します。
(b) その場で回転を行うのは少し難しい場合があります。少しスクラッチする場所が必要になります (おそらく 1 行または 1 列のサイズにほぼ等しい)。インプレース転置の実行に関する古い ACM 論文があります (http://doi.acm.org/10.1145/355719.355729)、しかしサンプルコードは goto 満載の厄介な FORTRAN です。
補遺:
http://doi.acm.org/10.1145/355611.355612 これは、おそらく優れた別のインプレース転置アルゴリズムです。
ニックさんの 答えは、(NxN とは対照的に) 少し変更するだけで、NxM 配列でも機能します。
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
これについて考える 1 つの方法は、軸の中心 (0,0) を左上隅から右上隅に移動したということです。単に一方から他方に移調しているだけです。
時間 - O(N)、空間 - O(1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
これが私の Ruby バージョンです (値は同じように表示されませんが、説明どおりに回転することに注意してください)。
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
出力：
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
これは Java による、正方形のみの空間内回転メソッドです。非正方形の 2D 配列の場合は、とにかく新しい配列を作成する必要があります。
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
新しい配列を作成して任意のサイズの 2 次元配列を回転するコード:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
ディンプルの +90 擬似コードの実装 (例:転置してから各行を反転します) JavaScript では次のようになります。
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
これを行うことができます 簡単な3ステップ:
1)行列があると仮定します。
1 2 3
4 5 6
7 8 9
2)行列の転置を計算します。
1 4 7
2 5 8
3 6 9
3)行を交換して回転行列を取得します
3 6 9
2 5 8
1 4 7
ジャワ ソースコード このために：
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
出力：
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
これは、C での私の実装です。メモリの複雑さは O(1)、インプレース回転、時計回りに 90 度です。
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix\n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("\n");
}
printf("\n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
Java のバージョンは次のとおりです。
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
この方法では、最初に最も外側の層を回転させ、次に内側の層に順番に移動します。
線形の観点から、行列を考えてみましょう。
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
今度は A をトランスポーズしてみましょう
1 4 7
A' = 2 5 8
3 6 9
そして、A' が B に及ぼす作用、または B が A' に及ぼす作用を考えてみましょう。
それぞれ：
7 4 1 3 6 9
A'B = 8 5 2 BA' = 2 5 8
9 6 3 1 4 7
これは、任意の n x n 行列に対して拡張可能です。そして、この概念をコードにすぐに適用します。
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
[n,m] 2D 配列を右に 90 度回転する C# コード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
結果：
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X は、グラフィックが含まれる配列のサイズです。
#transpose は Ruby の Array クラスの標準メソッドです。つまり、次のようになります。
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
実装は、C で書かれた n^2 転置関数です。ここで見ることができます:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose「トランスポーズ」の横にある「クリックしてソースを切り替え」を選択します。
O(n^2) 個の解よりも良い記憶がありますが、特別に構築された行列 (スパース行列など) のみです。
任意の M*N 行列の IN PLACE で時計回りに 90 度回転する行列の C コード
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
これはCでのIn Place実装です
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
これは、C での 2 ステップの解決策である行列 90 度回転の試みです。まず行列を所定の位置で転置し、次に列を交換します。
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("\n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
@ダゴリム:ああ、おい。私はこれを「退屈だ、何を考えようか」という良いパズルとしてずっとつかんでいました。私はインプレース転置コードを思いつきましたが、ここに来て、あなたのコードは私のものとほぼ同じであることがわかりました...ああ、そうですね。こちらはRuby版です。
require 'pp'
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
シンプルな C++ メソッドですが、大きな配列では大きなメモリ オーバーヘッドが発生します。
