Permutations
Pascal Triangle
Pascal Triangle
The obvious question when you see this, is how you generate the triangle. There are quite a few ways to generate this triangle, here are a few:
1. Generate the triangle using a formula
Apparently, there are a number of ways to do this. The first one is based on a formula and interestingly does not require any arrays as you might initially think.
Here is the formula for calculating the value at column c, row r, knowing the previous value at that row:
Another thing to notice is that the number of columns in each row is equal to the number of the row, so for example, in row 1 there is 1 column, in row 5 there are 5 columns, in row 8 there are 8 columns and so on.
The method below, takes the number of the rows to generate as a parameter and then outputs the number that make up the pascal triangle (although not in the triangular format).
public void generateTriangle( int maxRows )
{
int r, value;
for(int i=0; i<=maxRows; i++)
{
r = i+1; //this is the row
value = 1; //we start from col=1
for(int c=0; c<=i; c++)
{
//special case, cannot divide by 0
if(c>0)
{
value = value * (r - c) / c;
}
System.out.print(value + " ");
}
System.out.println();
}
}
2. Generate the triangle using a loop
public void generateTriagle2DArray(int maxRows)
{
int triangle[][] = new int[maxRows + 1][(maxRows + 1) * 2];
int leftOne, rightOne;
triangle[0][maxRows - 1] = 1;
leftOne = rightOne = maxRows - 1;
for (int i = 1; i < maxRows; i++)
{
leftOne--;
rightOne++;
triangle[i][leftOne] = 1;
triangle[i][rightOne] = 1;
for (int c = 1; c <= i; c++)
{
int left = triangle[i - 1][leftOne + (2 * c) - 1];
int right = triangle[i - 1][leftOne + (2 * c) + 1];
triangle[i][leftOne + (2 * c)] = left + right;
}
}
printTriangle2DArray(triangle);
}
public void printTriangle2DArray(int triangle[][])
{
for (int i = 0; i < triangle.length; i++)
{
for (int c = 0; c < triangle[i].length; c++)
{
if (triangle[i][c] == 0)
{
System.out.print(" ");
} else
{
System.out.print(triangle[i][c]);
}
}
System.out.println();
}
}
3. Generate the triangle using recursion
The method below, takes the row and the column of the number to generate and uses recursion to calculate what that number should be. Of course this means, there is a great deal of recursion going on, because for example, to calculate the number for row 3, column 3, you need to calculate row 2, col. 2 and row 2, col. 3, and each of these calculations will trigger a whole new series of recursive calculations.public int recrPascal(int row, int col)
{
int val1, val2, result = 0;
if (row == 0 || col == 0 || row == col + 1)
{
return 1;
}
val1 = recrPascal(row - 1, col - 1);
val2 = recrPascal(row - 1, col);
return val1 + val2;
}
And here is how you call the method above, to print the triangle:
public void printPascalRecursion(int maxRows)
{
for (int i = 0; i <= maxRows; i++)
{
for (int j = 0; j < i; j++)
{
System.out.print(recrPascal(i, j) + " ");
}
System.out.println();
}
}
For maxRows=8, here is what methods in (1) and (3) above will print:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
Method (2) will produce a nicer output since it stores the data in an array which can be later formatted in printTriangle2DArray. Nevertheless, the output is not completely justified because some numbers in the triangle have more than 1 digit.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1