Tuesday, January 31, 2012

InMemory Transpose of a sqaure matrix

/* swap every row with the corresponding column-- Let this step be called exchange
* After every exchange operation , size of matrix decreases by 1.
So further exchanges are to be made on this new reduced matrix.
So let suppose a 5 x 5 matrix, whose transpose we need to find
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

After first exchange( swapping values of row 0 with column 0 )
1 6 11 16 21
2 7 8 9 10
3 12 13 14 15
4 17 18 19 20
5 22 23 24 25

So the reduced matrix upon with subsequent exchanges are to made is a 4 x 4

7 8 9 10
12 13 14 15
17 18 19 20
22 23 24 25

Hence, the exchange Method has a loop 'for ( int k = i + 1; k < len; k++ ) {'

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}


**
*/

###### Complete Code #############################

public class TransposeOfMatrixInMemory {

public static void main( String[] args ) {
int[][] in1 = new int [][] {
{ 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 }

};
TransposeOfMatrixInMemory obj = new TransposeOfMatrixInMemory();
int[][] in = obj.transpose( in1 ) ;
for ( int i = 0 ;i < in.length; i++ ) {
for ( int j = 0; j < in[i].length ; j ++ ) {
System.out.print( in[i][j] + " " );
}
System.out.println();
}

}

/**
* Matrix is a square matrix
* @param in
* @return
*/
public int[][] transpose( int[][] in ) {
if ( in == null || in.length == 0 ) return null;

int [][] tmp = in;


int len = tmp.length;
for ( int i = 0; i < len; i++ ) {
tmp = interchange( i, in );
}
return tmp;
}

int[][] interchange( int i, int[][] in ) {
int[] tmp = in[i];

int len = tmp.length;
for ( int k = i + 1; k < len; k++ ) {

int a = in[k][i];
in[k][i] = in[i][k];
in[i][k] = a;

}
return in;

}



}

No comments:

Post a Comment