CODEWITHSUNDEEP
javaalgorithmmatrixtransposein-place
saltandwater
saltandwater

Reputation: 841

In-place matrix transpose of an M*N matrix in Java not possible?

Is it possible to do in-place matrix transpose of an M*N matrix in Java? I don't think it's possible in Java because, in a 3*5 matrix, the element at 3*5 would ideally be swapped with the element at 5*3, but such a position does not exist. In say, C/C++, it would be possible since memory is contiguous.

Also, there are other algorithms like the one posted here for M*N matrices, which I believe are not applicable to Java, but how's it any different from swapping elements at A[i][j] with A[j][i] since even the rolling window algorithm in the link above takes auxiliary memory?

Upvotes: 0

Views: 2769

Answers (3)

Checkmate
Checkmate

Reputation: 1154

You have to be careful with the term in-place. Strictly speaking, the transpose operator 'creates' a new matrix with potentially new dimensions. In the case of the article you linked, in-place just means using the same memory for the initial and final matrices, which is of course possible with a clever representation.

A trivial solution might be:

public class Matrix {
    private int[][] backingArray;
    private boolean transposed;
    public Matrix(int[][] _backingArray) {
        this.backingArray = _backingArray
    }

    public Matrix(int[] data, rows, columns) {
        backingArray = new int[rows][columns]
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < columns; j++)
                backingArray[i][j] = data[i*columns + j]
    }

    public int getElement(i, j) {
        if (transposed)
            return backingArray[j][i];
        return backingArray[i][j];
    }

    public void transpose() {
        transpose = !transpose;
    }
}

EDIT: Corrected some bad syntax

EDIT: Made it so that a 1-D matrix can be read in as per the OPs question (?)

Upvotes: 2

James_D
James_D

Reputation: 209330

Your question doesn't really make too much sense without specifying considerably more of the context: the algorithms are assuming a linear representation of the data (which, since languages such as C[++] essentially directly access memory, makes sense in those contexts). Note that for this kind of representation, you need to represent the number of rows and columns externally to the data. So the data representation for a 3x4 matrix could equally well be used for a 4x3 (or 2x6, etc) matrix, you would just have different values for numberCols and numberRows (in pseudocode). So the transposition algorithms here use the same memory allocation, but re-order the elements and re-interpret the number of rows and columns.

If you represent a (integer) matrix in Java as int[][], then you can't use the same algorithm, or indeed any in-place transposition, because the number of rows and columns are fixed for that particular representation: arrays in Java are not resizable. The algorithm doesn't apply because the data representation is not linear in the same way.

But if you chose to represent your matrix using a single-dimension array:

public class IntMatrix {

    private final int numColumns ;
    private final int numRows ;

    private final int[] data ;

    public IntMatrix(int numColumns, int numRows, int... data) {
        if (data.length != numColumns*numRows) {
            throw new IllegalArgumentException("...");
        }
        this.numColumns = numColumns ;
        this.numRows = numRows ;
        this.data = new data[numColumns * numRows] ;
        System.arrayCopy(data, 0, this.data, 0, this.data.length);
    }

    public int getElement(int row, int column) {
        return data[column*numRows+row];
    }

    public int getNumRows() {
        return numRows ;
    }

    public int getNumColumns() {
        return numColumns ;
    }
}

then you could certainly implement an in-place transpose with exactly the same algorithms.

However, you almost certainly wouldn't: you'd do the following:

public class IntMatrix {

    // code as before...

    public IntMatrix transpose() {
        return new Transpose(this);
    }

    private static class Transpose extends IntMatrix {
        private IntMatrix original ;
        Transpose(IntMatrix original) { 
            this.original = original ;
        }
        @Override
        public int getElement(int row, int column) {
            return original.getElement(column, row) ;
        }
        @Override
        public IntMatrix transpose() {
            return original ;
        }
        @Override
        public int getNumRows() {
            return original.getNumColumns();
        }
        @Override
        public int getNumColumns() {
            return original.getNumRows();
        }
    }
}

which (for this immutable representation) creates a transpose with O(1) operations and O(1) additional memory. You can create mutable representations similarly, with a little more work, and possibly higher cost depending exactly on what exact behavior you want (transpose view of the original mutable matrix, etc).

Upvotes: 1

alexgbelov
alexgbelov

Reputation: 3121

You're right, it can't. In Java, once an array has been created, its length is fixed. So, if M and N are different, you can't swap them

Upvotes: 0

Related Questions