Essential Algorithms: A Practical Approach to Computer Algorithms
Some applications can save space by using triangular arrays instead of normal rectangular arrays. In a triangular array, the values above the diagonal (where the item's column is greater than its row) have some default value, such as 0, null, or blank.
NOTE It's probably not worth going to the trouble of making a 3×3 triangular array, because you would save only three entries. In fact, it's probably not worth making a 100×100 triangular array, because you would save only 4,960 entries, which still isn't all that much memory, and working with the array would be harder than using a normal array. However, a 10,000×10,000 triangular array would save about 50 million entries, which begins to add up to real memory savings, so it may be worth making into a triangular array.
Building a triangular array isn't too hard. Simply pack the array's values into a one-dimensional array, skipping the entries that should not be included. The challenges are to figure out how big the one-dimensional array must be and to figure out how to map rows and columns to indices in the one-dimensional array.
http://eneuron.blogspot.com/2011/10/java-triangular-array-varying-sized.html
Can we achieve varied-size rows in a two dimensional array in Java language like in PHP and other languages?
Absolutely!
When a double dimensional array is instantiated like this
int[][] array = new int[n][m]
then all rows are of the same size m
Consider for example int[][] array = new int[10][5]
All rows in this double dimensional array would be of equal size 5.
But this is not what we need...we wanted varying-size rows in double dimensional array, right?
Here is the technique to produce varying-size row.
int[][] array = new int[10][];
Don't instantiate the column part of the array in order to be able to get varied size columns of the array later on.
like this...
array[0] = new int[1]; //row0 of size 1
array[1] = new int[2]; //row1 of size 2
array[2] = new int[3]; //row2 of size 3
.....
Take a look at below code which produces Triangular array
0
0 0
0 0 0
0 0 0 0
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Some applications can save space by using triangular arrays instead of normal rectangular arrays. In a triangular array, the values above the diagonal (where the item's column is greater than its row) have some default value, such as 0, null, or blank.
For example, a connectivity matrix represents the connections between points in some sort of network. The network might be an airline's flight network that indicates which airports are connected to other airports. The array's entry connected[i, j] is set to 1 if there is a flight from airport i to airport j. If you assume that there is a flight from airport j to airport iwhenever there is a flight from airport i to airport j, connected[i, j] = connected[j, i]. In that case there's no need to store both connected[i, j] and connected[j, i] because they are the same.
NOTE It's probably not worth going to the trouble of making a 3×3 triangular array, because you would save only three entries. In fact, it's probably not worth making a 100×100 triangular array, because you would save only 4,960 entries, which still isn't all that much memory, and working with the array would be harder than using a normal array. However, a 10,000×10,000 triangular array would save about 50 million entries, which begins to add up to real memory savings, so it may be worth making into a triangular array.
Building a triangular array isn't too hard. Simply pack the array's values into a one-dimensional array, skipping the entries that should not be included. The challenges are to figure out how big the one-dimensional array must be and to figure out how to map rows and columns to indices in the one-dimensional array.
http://eneuron.blogspot.com/2011/10/java-triangular-array-varying-sized.html
Can we achieve varied-size rows in a two dimensional array in Java language like in PHP and other languages?
Absolutely!
When a double dimensional array is instantiated like this
int[][] array = new int[n][m]
then all rows are of the same size m
Consider for example int[][] array = new int[10][5]
All rows in this double dimensional array would be of equal size 5.
But this is not what we need...we wanted varying-size rows in double dimensional array, right?
Here is the technique to produce varying-size row.
int[][] array = new int[10][];
Don't instantiate the column part of the array in order to be able to get varied size columns of the array later on.
like this...
array[0] = new int[1]; //row0 of size 1
array[1] = new int[2]; //row1 of size 2
array[2] = new int[3]; //row2 of size 3
.....
Take a look at below code which produces Triangular array
0
0 0
0 0 0
0 0 0 0
0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
public static void TriangularArray(int maxRow){ int[][] triangle; // instantiating only row part of the array (total number of rows) triangle = new int[maxRow][]; // Now instantiate individual columns separately with different sizes and assign them to rows for (int r=0; r < triangle.length; r++) { triangle[r] = new int[r+1]; } // Print the triangular array for (int r=0; r<triangle.length; r++) { for (int c=0; c<triangle[r].length; c++) { System.out.print(" " + triangle[r][c]); } System.out.println(""); } } |
public static void main(String [] args) {
int [][] tri = new int[20][];
for (int r=0; r<tri.length; r++) {
tri[r] = new int[r+1];
tri[r][0] = 1;
tri[r][r] = 1;
for (int c=1; c<r; c++) {
tri[r][c] = tri[r-1][c]+tri[r-1][c-1];
}
}
for (int r=0; r<tri.length; r++) {
for (int c=0; c<tri[r].length; c++) {
System.out.print(" "+tri[r][c]);
}
System.out.println("");
}
}
}
int [][] tri = new int[20][];
for (int r=0; r<tri.length; r++) {
tri[r] = new int[r+1];
tri[r][0] = 1;
tri[r][r] = 1;
for (int c=1; c<r; c++) {
tri[r][c] = tri[r-1][c]+tri[r-1][c-1];
}
}
for (int r=0; r<tri.length; r++) {
for (int c=0; c<tri[r].length; c++) {
System.out.print(" "+tri[r][c]);
}
System.out.println("");
}
}
}
