Learning Project 2

[Ted Scofield]

Hi, me again.

The next program computes the determinant of an n x n matrix using Laplace expansion on the first row. It uses recursive calls to compute minors. The code itself is probably really bad, but that's where you guys step in and suggest improvements.

This one does not have a GUI, you have to manually insert the matrix as an multidimensional array (int[][]). If you have any suggestions on how the GUI should look like, let me know.

Here's the code:

  
public class Det {
	
	private int[][] matrix;
	
	public Det(int[][] matrix) {
		this.matrix = matrix;
	}
	
	private int computeDet(int[][] matrix) {
		int matrixSize = matrix.length;
		if (matrixSize == 2) {
			return matrix[0][0]*matrix[1][1] - matrix[0][1]*matrix[1][0];
		} else {
			int value = 0;
			for (int i = 0; i < matrixSize; i++) {
				int[][] minor = generateMinor(matrix,0,i);				// Laplace on row 1
				value += (sgn(i)*matrix[0][i])*computeDet(minor);
			}
			return value;
		}
	}
	
	private int sgn(int n) {											// makes a cofactor positive or negative
		if (n % 2 == 0) {
			return 1;
		} else {
			return -1;
		}
	}
	
	private int[][] generateMinor(int[][] matrix, int row, int column) {		// this method generates a minor
		int matrixSize = matrix.length;
		int minorSize = matrixSize - 1;
		int counterOne = 0;
		int counterTwo = 0;
		int[][] minor = new int[minorSize][minorSize];
		
		for (int i = 0; i < matrixSize; i++) {
			if (i == row) {
				continue;
			}
			for (int j = 0; j < matrixSize; j++) {
				if (j == column) {
					continue;
				} 
				minor[counterOne][counterTwo] = matrix[i][j];
				++counterTwo;
				
			}
			++counterOne;
			counterTwo = 0;
		}
		return minor;
	}
	
	public void matrixToString(int[][] matrix) {							// prints the matrix if needed
		int size = matrix.length;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				System.out.print(matrix[i][j]+" ");
			}
			System.out.println();
		}
	}
	
	public static void main(String[] args) {
		
		int[][] mat = {{1,0,0},{0,1,0},{0,0,1}};						// this is how you input the matrix
		Det d = new Det(mat);
		System.out.println(d.computeDet(mat));
	}
}
  

[Joanne Neal]

Will your matrix always be n x n (i.e. will it always be a square matrix) ?
I only ask because your generateMinor and matrixTostring methods won't work with a non-square matrix.

And just a personal preference of mine, but there is no need to assign the length of the array to a variable

for (int i = 0; i < matrix.length; i++) {

is better than

for (int i = 0; i < size; i++) { 

because it's obvious what the delimiter of your for loop is. You don't have to find out where size is set and it also avoids the possibility of it being accidentally set to the wrong value.

[Ted Scofield]

Hi Joanne,

the determinant of a matrix is only defined when the matrix is square, so the number of rows must match the number of columns.
I use

for (int i = 0; i < size; i++)

instead of

for (int i = 0; i < matrix.length; i++) 

because the length of a matrix is calculated only once whereas in your case, the matrix length will be calculated in every iteration.

Thank you for you comment. Do you have any idea on how to set the GUI?

[Fred Hamilton]

Ted Scofield wrote:
...

the length of a matrix is calculated only once whereas in your case, the matrix length will be calculated in every iteration.

...

I'm not so sure that applies here, it is my understanding that length is not a function but a property of the arrray, a field in which a value is stored. and therefore it is not recalculated with each iteration of the loop.

something like string.length() or ArrayList.size() perhaps is a different story cause length() and size() are functions.

instead of looping explixitly on the array indexes, you can also specify an array loop as follows for (int item : numbers), where numbers is an array of type int[]. Not sure if this method will work here though.

here is a reference for this other type of for loop.

http://java.sun.com/docs/books/tutorial/java/nutsandbolts/for.html

[Campbell Ritchie]

If you are using matrices, it is worthwhile checking that the array is "rectangular".

When the array is presented to your constructor, iterate through it and check that the length of each element is the same. If you need a square array, that would require an additional check for the first element, then all the elements must have the same length. Beware in case you ever encounter a 0-length array!

Arrays, Strings (which actually hide an array in their depths) and Lists all have a field (directly or indirectly) which measures how many elements they contain. In the case of arrays and Strings, it never changes, but in Lists it does change. The String#length() and List#size() methods simply return that field, without having to do any more calculations. The List size field is recalculated whenever elements are added or removed.

[Fred Hamilton]

Campbell Ritchie wrote:If you are using matrices, it is worthwhile checking that the array is "rectangular".

When the array is presented to your constructor, iterate through it and check that the length of each element is the same. If you need a square array, that would require an additional check for the first element, then all the elements must have the same length. Beware in case you ever encounter a 0-length array!

Arrays, Strings (which actually hide an array in their depths) and Lists all have a field (directly or indirectly) which measures how many elements they contain. In the case of arrays and Strings, it never changes, but in Lists it does change. The String#length() and List#size() methods simply return that field, without having to do any more calculations. The List size field is recalculated whenever elements are added or removed.

Campbell, I'm learning here, so I don't want to come across as argumentative, but you have commented "If you are using matrices, it is worthwhile checking that the array is "rectangular" First of all I am not sure what you mean by "make sure each element has the same length" Since matrix is defined as int[][], wouldn't that automatically guarantee that the array is rectangular, ie all rows have the same length and all cols have the same length? Am i missing something?

Also, in your list paragraph, when you speak of Lists, does that apply equally to the ArrayList object, or are you referring to some other kind of construct.

regards
Fred.

[Brian Legg]

Fred Hamilton wrote:Since matrix is defined as int[][], wouldn't that automatically guarantee that the array is rectangular, ie all rows have the same length and all cols have the same length? Am i missing something?

There is no such thing as a multi-dimensional array in Java, just an Array of Arrays. That being said with a definition of int[][] you could assign an int array of size 10 to element 0 and an int array of size 200 to element 1 and so on. As long as each array is an array of ints then it can be assigned to an element in an array of int arrays. Basically you are creating an standard array which holds integer arrays, each integer array does not need to be the same size.

[Fred Hamilton]

Brian Legg wrote:

Fred Hamilton wrote:Since matrix is defined as int[][], wouldn't that automatically guarantee that the array is rectangular, ie all rows have the same length and all cols have the same length? Am i missing something?

There is no such thing as a multi-dimensional array in Java, just an Array of Arrays. That being said with a definition of int[][] you could assign an int array of size 10 to element 0 and an int array of size 200 to element 1 and so on. As long as each array is an array of ints then it can be assigned to an element in an array of int arrays. Basically you are creating an standard array which holds integer arrays, each integer array does not need to be the same size.

wow, ok learned something there, I can see I have some research to do. I assume when you use the word element then, you are referring to a row or a column in the case if int[][]. That I did not pick up on at first, I assumed incorrectly that an element would be that which had both a row and a column co-ordinate.

[Brian Legg]

I try not to think of it in terms of rows and columns. When I say "element" what I am refering to depends on the context. An element of an int[][] would be an int array (aka int[]). An element of that int[] would be an int. An element was just my way of refering to the smallest container or bucket for that particular array. If I am refering to an int[][] it has no int elements, just arrays of ints. This is the distinction when it comes to other popular languages. Long live OOP ;)

[Campbell Ritchie]

Brian's answers are always helpful

. . . and about Lists, have a look in the Java™ Tutorials, particularly the bits about "List interface" and "List implementations".

[Fred Hamilton]

Thanks man, I'll add lists to my list. Right now I have about 3 years worth of stuff to research, at least.

[Campbell Ritchie]

You're welcome I expect you to have read all that lot by next week