- Как транспонировать матрицу в java
- Транспонирование матрицы в Java
- Решение:
- Transpose of a Matrix in Java
- Introduction to Transpose of a Matrix in Java
- Algorithm to Find Transpose of a Matrix in Java
- Example 1: Java Program to Find Transpose of a Matrix
- Time and Space Complexity
- Example 2: For Square Matrix
- Example 3: For Rectangular Matrix
- Example 4: In-Place for Square Matrix
- Algorithm
- Conclusion
- Транспонирование матрицы в Java
- Решение:
Как транспонировать матрицу в java
Чтобы транспонировать матрицу необходимо поменять местами столбцы и строки :
int[][] arr = 1,2,3,4>, 5,6,7,8>>; int rows = arr.length; int columns = arr[0].length; int[][] transposedArr = new int[columns][rows]; for(int i = 0; i rows; i++) for(int j = 0; j columns; j++) transposedArr[j][i] = arr[i][j]; > > System.out.println(Arrays.deepToString(transposedArr)); // => [[1, 5], [2, 6], [3, 7], [4, 8]] Транспонирование матрицы в Java
Напишите программу Transpose.java, которая будет транспонировать заданную квадратную матрицу без использования дополнительного массива. Напоминаем, что такое транспонирование матрицы. Транспонированная матрица — это матрица, полученная из исходной матрицы путем замены строк на столбцы. Ниже приводим 2 примера транспонированной матрицы.
Решение:
Часть 1 — создаем матрицу n на n и заполняем ее значениями с помошью цикла. При желании можно сделать так, чтобы число n задавалось пользователем с консоли. Не бойтесь цикла 🙂
Вы увидите, что выражение » a[i][j] = n*i + j » просто заполняет массив по порядку числами , начиная с 0. Часть 2 — выводит на экран двухмерную матрицу с помощью двух массивов. «%4d» значит «4 пробела». Так, «%3d» — это 3 пробела, «%6d» — 6 пробелов, и т.д.
Часть 3 — транспонирование матрицы. Это «переворачивание» матрицы:
А еще во время транспонирования номер столбца и номер строки «меняются местами». Например, было a[1] [9], стало a[9][1]. И так со всеми элементами (a[2] [2], конечно, остается a[2][2]). Этим и пользуются для того, чтобы транспонировать матрицу в этом примере:
a[i][j] и a[j][i] меняются местами с помощью переменной temp (temporary — временный).
Часть 4 — выводим транспонированную матрицу на экран. Повторяет часть 2.
Надеемся — наша статья была Вам полезна. Есть возможность записаться на наши курсы по Java. Детальную информацию смотрите у нас на сайте.
Transpose of a Matrix in Java
Transpose of a matrix in Java is obtained by interchanging all rows to columns and columns to rows. This means that in the transpose of a matrix, rows in the normal matrix become the columns, and columns form the rows. If the dimension of the original matrix is m × n m\times n m × n , the dimension of the transpose matrix will be n × m n\times m n × m .
The transpose of a matrix can be computed by assigning [ i ] [ j ] [i][j] [ i ] [ j ] element in the transpose matrix equal to the [ j ] [ i ] [j][i] [ j ] [ i ] in the original matrix.
Introduction to Transpose of a Matrix in Java
Transpose of a matrix in Java is obtained by interchanging its rows into columns or columns into rows. This means that in the transpose of a matrix, rows in the normal matrix become the columns, and columns form the rows.
Let us look at an example. If the given matrix is:
2 5 3 8 1 2 6 6 6 4 1 1 6 4 2 9 \begin
Let us denote this matrix as M . Clearly this is a 3 × 4 3\times4 3 × 4 matrix, as it has three rows and four columns. If we try to write the transpose of this matrix in Java, it will be something like:
2 1 2 1 5 6 6 1 6 3 6 4 2 8 4 9 \begin
If you compare the two matrices, the rows of the previous matrix M have now become the columns in this transpose matrix, and the columns have become rows. Clearly, this matrix denoted as M T is a 4 × 3 4\times3 4 × 3 matrix, as it has four rows and three columns.
But how do find the transpose of a matrix in Java? Let us discuss the algorithm in the next section.
Algorithm to Find Transpose of a Matrix in Java
We already saw that if we have a matrix M having n n n rows and m m m columns, then its transpose, M T will have m m m rows and n n n columns.
Let us look at how the elements change when a matrix is converted to its transpose using the following matrix M :
t 1 1 t 1 2 t 1 3 t 1 4 t 2 1 t 2 2 t 2 3 t 2 4 t 3 1 t 3 2 t 3 3 t 3 4 \begin
Here t i j tij t i j denotes the matrix element present at i t h ith i t h row and j t h jth j t h column. Now let us look at how the indices change in the transpose of this matrix. The transpose matrix M T is given as:
t 1 1 t 2 1 t 3 1 t 1 2 t 2 2 t 3 2 t 1 3 t 2 3 t 3 3 t 1 4 t 2 4 t 3 4 \begin
Looking at the example, it is clear we just need to replace the rows with the column values and the columns with the row values. That means if an element is at the index [ i , j ] [ i , j ] in the original matrix M, then in the transpose matrix M T it will be at the index [ j , i ] [ j , i ] .
Hence, in the code of converting a matrix to its transpose, we first need extra space for another 2-d matrix which will store the transpose of the matrix.
Then, in this new transpose matrix, we only need to assign the element at index [ i ] [ j ] [i][j] [ i ] [ j ] in the original matrix to the element [ j ] [ i ] [j][i] [ j ] [ i ] in the transpose matrix. This operation has to performed for every element of the original matrix. We can achieve this by iterating through every element of the matrix using two nested for loops.
Formally, the algorithm to find the transpose of a matrix will be:
- Create a two-dimensional integer array M_transpose[][] of size ( m,n ) where n is the number of rows and m the number of columns in the original matrix.
- Traverse the original matrix M[][] and for each element M[i][j] , assign M_transpose[j][i] = M[i][j] .
- M_transpose[][] is the required transpose matrix.
Let us look at the formal code to find the transpose of a matrix using a few examples in the next sections.
Example 1: Java Program to Find Transpose of a Matrix
Given a matrix, let us look at the code to find its transpose in Java.
Following the above-defined algorithm, we can successfully find the transpose of a matrix in Java.
Time and Space Complexity
- The time complexity for this solution is O ( n ∗ m ) O(n*m) O ( n ∗ m ) where n n n is the number of rows in the matrix, and m m m is the number of columns.
- The space complexity is also O ( n ∗ m ) O(n * m) O ( n ∗ m ) , where n n n is the number of rows in the matrix and m m m is the number of columns, which is used to store the values in the transpose matrix.
Example 2: For Square Matrix
We saw the code for an arbitrary 2-d matrix, but what if the matrix we have is a square matrix. A square matrix is a matrix that has the same number of rows and columns. This means that if n n n is the number of rows and m m m is the number of columns in a matrix, then for a square matrix, n = m n=m n = m .
The only change this will bring in the original algorithm is that our transpose matrix will have the same size as the original matrix, i.e. of size (n, n) . After that, the algorithm stays the same, we just have to iterate over all the elements of the original matrix and assign M_transpose[j][i] = M[i][j] .
Let us look at the code to find the transpose of a square matrix in java.
Time and Space Complexity
- The time complexity for this solution is O ( n 2 ) O(n^2) O ( n 2 ) where n n n is the number of rows/columns in the square matrix.
- The space complexity is also O ( n 2 ) O(n^2) O ( n 2 ) where n n n is the number of rows/columns in the matrix, which is used to store the values in the transpose matrix.
Example 3: For Rectangular Matrix
Let us see what the code will look like for a rectangular matrix, in which the number of rows is not equal to the number of columns. This means that if n n n is the number of rows and m m m is the number of columns in a matrix, then for a rectangular matrix, n ! = m n != m n ! = m .
Time and Space Complexity
- The time complexity for this solution is O ( n ∗ m ) O(n*m) O ( n ∗ m ) where n n n is the number of rows in the matrix, and m m m is the number of columns.
- The space complexity is also O ( n ∗ m ) O(n*m) O ( n ∗ m ) , where n n n is the number of rows in the matrix and m m m is the number of columns, which is used to store the values in the transpose matrix.
Example 4: In-Place for Square Matrix
For a square matrix, we can reduce the space complexity by not making a different matrix to store the transpose, but instead making changes in the original matrix itself.
Only possible for square matrices:
- We can do this in-place conversion for a square matrix only because the number of rows of a square matrix is equal to the number of columns, and because of this the size of the original and the transpose matrix is the same.
- But this is not the case with any other matrix which has different number of rows and columns.
Algorithm
- To obtain the transpose matrix in-place, we do not have to create any new matrix to store the transpose values.
- What we have to do instead is just swap the values of M [ i ] [ j ] M[i][j] M [ i ] [ j ] with M [ j ] [ i ] M[j][i] M [ j ] [ i ] for all 0
- This means, we are going to do the same thing that we used to do earlier, with the only exception being that this time we swap M [ i ] [ j ] M[i][j] M [ i ] [ j ] with M [ j ] [ i ] M[j][i] M [ j ] [ i ] instead of assigning M [ j ] [ i ] M[j][i] M [ j ] [ i ] = M [ i ] [ j ] M[i][j] M [ i ] [ j ] .
- Though we are traversing only half the matrix, but in each swap operation we are handling two positions in the matrix. Thus effectively it covers the whole matrix.
This is done because if we are transforming the original square matrix itself, then the values lying above the main diagonal need to be swapped with those lying below it, as shown in the diagram below.
Let us look at the code for finding the transpose of a square matrix in java in-place.
Time and Space Complexity
- The time complexity for this solution is O ( n 2 ) O(n^2) O ( n 2 ) where n n n is the number of rows/columns in the square matrix. This is because this time our matrix is a square matrix of size ( n,n ) and we iterate over it once.
- The space complexity is O ( 1 ) O(1) O ( 1 ) , as we perform the operations in-place.
Conclusion
- Transpose of any matrix in Java is obtained by interchanging all rows to columns and columns to rows.
- If we have a matrix M having n n n rows and m m m columns, then its transpose, M T will have m m m rows and n n n columns.
- To find the transpose of a matrix in Java, assign the element at index [ i ] [ j ] [i][j] [ i ] [ j ] in the orinial matrix to the element [ j ] [ i ] [j][i] [ j ] [ i ] in transpose matrix.
- The time and space complexity is O ( n ∗ m ) O(n*m) O ( n ∗ m ) where n n n is the number of rows in the matrix, and m m m is the number of columns.
- We can find the transpose of a square matrix in Java in place also, reducing the space complexity to O ( 1 ) O(1) O ( 1 ) .
- In-place algorithm to find transpose matrices is possible only in case of square matrices.
Транспонирование матрицы в Java
Напишите программу Transpose.java, которая будет транспонировать заданную квадратную матрицу без использования дополнительного массива. Напоминаем, что такое транспонирование матрицы. Транспонированная матрица — это матрица, полученная из исходной матрицы путем замены строк на столбцы. Ниже приводим 2 примера транспонированной матрицы.
Решение:
Часть 1 — создаем матрицу n на n и заполняем ее значениями с помошью цикла. При желании можно сделать так, чтобы число n задавалось пользователем с консоли. Не бойтесь цикла 🙂
Вы увидите, что выражение » a[i][j] = n*i + j » просто заполняет массив по порядку числами , начиная с 0. Часть 2 — выводит на экран двухмерную матрицу с помощью двух массивов. «%4d» значит «4 пробела». Так, «%3d» — это 3 пробела, «%6d» — 6 пробелов, и т.д.
Часть 3 — транспонирование матрицы. Это «переворачивание» матрицы:
А еще во время транспонирования номер столбца и номер строки «меняются местами». Например, было a[1] [9], стало a[9][1]. И так со всеми элементами (a[2] [2], конечно, остается a[2][2]). Этим и пользуются для того, чтобы транспонировать матрицу в этом примере:
a[i][j] и a[j][i] меняются местами с помощью переменной temp (temporary — временный).
Часть 4 — выводим транспонированную матрицу на экран. Повторяет часть 2.
Надеемся — наша статья была Вам полезна. Есть возможность записаться на наши курсы по Java. Детальную информацию смотрите у нас на сайте.