How to rotate a N x N matrix by 90 degrees?
for(int i=0; i<n/2; i++)
for(int j=0; j<(n+1)/2; j++)
cyclic_roll(m[i][j], m[n-1-j][i], m[n-1-i][n-1-j], m[j][n-1-i]);
void cyclic_roll(int &a, int &b, int &c, int &d)
{
int temp = a;
a = b;
b = c;
c = d;
d = temp;
}
Note I haven't tested this, just compoosed now on the spot. Please test before doing anything with it.
How to rotate a matrix 90 degrees without using any extra space?
let a be an nxn array 0 based indexing
f = floor(n/2)
c = ceil(n/2)
for x = 0 to f - 1
for y = 0 to c - 1
temp = a[x,y]
a[x,y] = a[y,n-1-x]
a[y,n-1-x] = a[n-1-x,n-1-y]
a[n-1-x,n-1-y] = a[n-1-y,x]
a[n-1-y,x] = temp
Edit If you want to avoid using temp, this works (it also rotates in the correct direction) this time in python.
def rot2(a):
n = len(a)
c = (n+1) / 2
f = n / 2
for x in range(c):
for y in range(f):
a[x][y] = a[x][y] ^ a[n-1-y][x]
a[n-1-y][x] = a[x][y] ^ a[n-1-y][x]
a[x][y] = a[x][y] ^ a[n-1-y][x]
a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-x][n-1-y] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-y][x] = a[n-1-y][x] ^ a[n-1-x][n-1-y]
a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
a[y][n-1-x] = a[n-1-x][n-1-y]^a[y][n-1-x]
a[n-1-x][n-1-y] = a[n-1-x][n-1-y]^a[y][n-1-x]
Note: This only works for matrices of integers.
Rotate NxN Matrix Counter(anti)-Clockwise 90 Degress
If you reverse the order of each individual row and then taken rows in opposite order from a clockwise rotation, you get a count-clockwise rotation.
A B C G D A A D G C F I
D E F -> Clockwise -> H E B -> Reverse -> B E H -> Opposite -> B E H
G H I I F C Rows C F I Ordering A D G
Matrix Counter
Clockwise
Usually it's easier (and more computationally efficient) to do a clockwise rotation rotation on the original matrix in reverse order if you already have a clockwise rotating algorithm available.
1 2 3 9 8 7 3 6 9
4 5 6 -> Reverse -> 6 5 4 -> Clockwise -> 2 5 8
7 8 9 Indices 3 2 1 1 4 7
Matrix Counter
Clockwise
You can also just take 3 clockwise rotations to get to a counter clockwise rotation.
Though in reality it's usually fairly easy to edit the clockwise algorithm to your purposes directly. So I'd only use the above options if you don't care about efficiency and don't want to work through the logic of changing the direction of rotation.
How do I rotate a matrix 90 degrees counterclockwise in java?
If you draw out the matrix to visualize, you'll see that some of your indices are off. For example, instead of using matrix.length-1, you should use bottom in your updates because the size of the layer's square will decrease as i increases. Another error is that in your second update, you should have:
matrix[j][bottom] = matrix[bottom][bottom - (j - top)];
instead of:
matrix[j][bottom] = matrix[bottom][j];
This is because in the bottom row of the layer the indices start from the last column and move backward to the first column. j - top indicates how far along you are in the top row of your layer.
After drawing out the matrix, I found the correct updates to be as follows:
public static void main(String[] args) {
int n = 5;
int[][] a = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
a[i][j] = i * n + j + 1;
}
}
rotateMatrix(a);
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
System.out.printf("%3d", a[i][j]);
}
System.out.println();
}
}
public static void rotateMatrix(int[][] matrix) {
if (matrix.length == 0) {
return;
}
for (int i = 0; i < matrix.length / 2; i++) {
int top = i;
int bottom = matrix.length - 1 - i;
for (int j = top; j < bottom; j++) {
int temp = matrix[top][j];
matrix[top][j] = matrix[j][bottom];
matrix[j][bottom] = matrix[bottom][bottom - (j - top)];
matrix[bottom][bottom - (j - top)] = matrix[bottom - (j - top)][top];
matrix[bottom - (j - top)][top] = temp;
}
}
}
Output:
5 10 15 20 25
4 9 14 19 24
3 8 13 18 23
2 7 12 17 22
1 6 11 16 21
Matrix NxN rotation 90 degrees - is it possible to do it better than O(n^2)?
Well, if you can freely control the representation of your Matrix, i can give you one in O(1) :).
Let's say your matrix is in an object that fulfills the interface IMatrix
interface IMatrix
{
double getValue(int index_x, int index_y);
void setValue(int index_x, int index_y, double value);
}
You can implement that in different ways, for instance:
class RowBasedMatrix implements IMatrix
{
//an array of rows
double[][] values;
//size of the Matrix
int N;
//this is explained later
bool invert_x, invert_y;
RowBasedMatrix(double[][] values, int N, bool invert_x, bool invert_y)
{
this.values = values;
this.N = N;
this.invert_x = invert_x;
this.invert_y = invert_y;
}
double getValue(int index_x, int index_y)
{
if(invert_x)
index_x = N - 1 - index_x
if(invert_y)
index_y = N - 1 - index_y
return values[index_y][index_x];
}
double setValue(int index_x, int index_y, double value)
{
if(invert_x)
index_x = N - 1 - index_x
if(invert_y)
index_y = N - 1 - index_y
values[index_y][index_x] = value;
}
}
class ColumnBasedMatrix implements IMatrix
{
//an array of columns
double[][] values;
//size of the Matrix
int N;
//this is explained later
bool invert_x, invert_y;
RowBasedMatrix(double[][] values, int N, bool invert_x, bool invert_y)
{
this.values = values;
this.N = N;
this.invert_x = invert_x;
this.invert_y = invert_y;
}
double getValue(int index_x, int index_y)
{
if(invert_x)
index_x = N - 1 - index_x
if(invert_y)
index_y = N - 1 - index_y
return values[index_x][index_y];
}
double setValue(int index_x, int index_y, double value)
{
if(invert_x)
index_x = N - 1 - index_x
if(invert_y)
index_y = N - 1 - index_y
values[index_x][index_y] = value;
}
}
The idea is: you can reuse the values array from a RowBasedMatrix into the values of a ColumnBasedMatrix that is now effectively a Matrix with a value base mirrored at the diagonal from (1,1) to (N,N).
If you invert the x- or y-indices you can create a rotated Matrix. (Again inverting does not copy stuff around, but modifies the getValue and setValue Functions to access other fields).
If you transform a row-Based matrix into a column-based one, and then invert the x-coordinate, you effectively have a 90° clockwise rotated Matrix.
EDIT: expanded Example code
EDIT 2: an example code using the Matrix classes.
double[][] raw matrix_data =
new double[][] { {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}
{3.0, 3.1, 3.2, 3.3, 3.4}
{4.0, 4.1, 4.2, 4.3, 4.4} };
int main(...)
{
//this Matrix returns the values as visible above
IMatrix default = new RowBasedMatrix(matrix_data, 5, false, false)
double test = default.getValue(0, 4);
//test is set to 4.0
test = default.getValue(3, 1);
//test is set to 1.3
//this Matrix return values as if it had this value set:
// /0.4, 0.3, 0.2, 0.1, 0.0\
// | 1.4, 1.3, 1.2, 1.1, 1.0 |
// | 2.4, 2.3, 2.2, 2.1, 2.0 |
// | 3.4, 3.3, 3.2, 3.1, 3.0 |
// \4.4, 4.3, 4.2, 4.1, 4.0/
IMatrix xInverted = new RowBasedMatrix(matrix_data, 5, true, false);
test = xInverted.getValue(0, 4);
//test is set to 4.4
test = xInverted.getValue(3, 1);
//test is set to 1.1
//now, if we use the column-matrix (switch x- and y-coordinates):
// /0.0, 1.0, 2.0, 3.0, 4.0\
// | 0.1, 1.1, 2.1, 3.1, 4.1 |
// | 0.2, 1.2, 2.2, 3.2, 4.2 |
// | 0.3, 1.3, 2.3, 3.3, 4.3 |
// \0.4, 1.4, 2.4, 3.4, 4.4/
IMatrix columns = new ColumnBasedMatrix(matrix_data, 5, false, false);
test = columns.getValue(0, 4);
//test is set to 0.4
test = columns.getValue(3, 1);
//test is set to 3.1
//if we invert this matrix's x-coordinates again, we get a 90° clockwise rotated value set
IMatrix rotated = new ColumnBasedMatrix(matrix_data, 5, true, false);
}
This implementation is not copying any values around (which would cost O(n^2)).
Instead it makes a small O(1) calculation every time a value is accessed.
(Please note, that my implementation is not perfect and, for instance, does not work on non-square matrices)
Explain an algorithm to rotate a N X N matrix by 90 degree
Submitted for your approval. Run it as is and study the output and think about running bases clockwise. Seriously.
Let me know if it helped. It was fun to explore for me.
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
public class NewMain1 {
static int[][] m ;
public static void rotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;
int last = n - 1 - layer;
for(int i = first; i < last; ++i) {
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last-offset][first];
printmove(last-offset,first,first,i);
// bottom -> left
printmove(last,last-offset,last-offset,first);
matrix[last-offset][first] = matrix[last][last - offset];
// right -> bottom
printmove(i,last,last,last-offset);
matrix[last][last - offset] = matrix[i][last];
// top -> right
printmove(first,i,i,last);
matrix[i][last] = top; // right <- saved top
System.out.println("");
printmatrix(matrix,n);
System.out.println("");
try{
int s = System.in.read();
} catch (IOException ex){ }
}
}
}
static void printmove(int r1, int c1, int r2, int c2){
System.out.println("["+(r1+1)+"]["+(c1+1)+ "] moves to [" + (r2+1) + "][" + (c2+1) + "]");
}
static void printmatrix(int[][] m, int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(m[i][j] + " ");
}
System.out.println("");
}
}
static void makematrix(int[][] m, int n){
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
m[i][j] = 10*(i+1) + j+1;
}
}
}
public static void main(String[] args) {
int n = 6;
int[][] m = new int[n][n];
makematrix(m, n);
printmatrix(m, n);
rotate(m,n);
System.out.println("");
printmatrix(m, n);
}
}
E.g.:
Logical Error in rotating a NxN matrix by 90 degree in place
I have modified your program a little bit and now it works. I have provided codes for rotating the matrix by 90 degrees on left as well as right. Have a look.
for (i = 0; i < n / 2; i++) {
for (j = i; j < n - 1 - i; j++) {
//Rotating left by 90 degrees
temp = a[i][j];
a[i][j] = a[j][n - 1 - i];
a[j][n - 1 - i] = a[n - 1 - i][n - 1 - j];
a[n - 1 - i][n - 1 - j] = a[n - 1 - j][i];
a[n - 1 - j][i] = temp;
/*
//Rotating right by 90 degrees
temp = a[i][j];
a[i][j] = a[n - 1 - j][i];
a[n - 1 - j][i] = a[n - 1 - i][n - 1 - j];
a[n - 1 - i][n - 1 - j] = a[j][n - 1 - i];
a[j][n - 1 - i] = temp;
*/
}
}
Rotate a Matrix in R by 90 degrees clockwise
t does not rotate the entries, it flips along the diagonal:
x <- matrix(1:9, 3)
x
## [,1] [,2] [,3]
## [1,] 1 4 7
## [2,] 2 5 8
## [3,] 3 6 9
t(x)
## [,1] [,2] [,3]
## [1,] 1 2 3
## [2,] 4 5 6
## [3,] 7 8 9
90 degree clockwise rotation of R matrix:
You need to also reverse the columns prior to the transpose:
rotate <- function(x) t(apply(x, 2, rev))
rotate(x)
## [,1] [,2] [,3]
## [1,] 3 2 1
## [2,] 6 5 4
## [3,] 9 8 7
rotate(rotate(x))
## [,1] [,2] [,3]
## [1,] 9 6 3
## [2,] 8 5 2
## [3,] 7 4 1
rotate(rotate(rotate(x)))
## [,1] [,2] [,3]
## [1,] 7 8 9
## [2,] 4 5 6
## [3,] 1 2 3
rotate(rotate(rotate(rotate(x))))
## [,1] [,2] [,3]
## [1,] 1 4 7
## [2,] 2 5 8
## [3,] 3 6 9
90 degree counter clockwise rotation of R matrix:
Doing the transpose prior to the reverse is the same as rotate counter clockwise:
foo = matrix(1:9, 3)
foo
## [,1] [,2] [,3]
## [1,] 1 4 7
## [2,] 2 5 8
## [3,] 3 6 9
foo <- apply(t(foo),2,rev)
foo
## [,1] [,2] [,3]
## [1,] 7 8 9
## [2,] 4 5 6
## [3,] 1 2 3
Related Topics
Enum VS Constexpr for Actual Static Constants Inside Classes
What Does an Ampersand After This Assignment Operator Mean
Image Edge Smoothing with Opencv
Calling a Function Through Its Address in Memory in C/C++
Using Std::Move() When Returning a Value from a Function to Avoid to Copy
Qtcpsocket: Reading and Writing
Difference Between A* Pa = New A; and A* Pa = New A();
Erase/Remove Contents from the Map (Or Any Other Stl Container) While Iterating It
C++ [Windows] Path to the Folder Where the Executable Is Located
What Is Assignment via Curly Braces Called? and Can It Be Controlled
How to Break Shared_Ptr Cyclic Reference Using Weak_Ptr
When Do Programmers Use Empty Base Optimization (Ebo)
How Make File* from Handle in Winapi
Interesting Behavior of Compiler with Namespaces
Branchless Code That Maps Zero, Negative, and Positive to 0, 1, 2