Einstein Einstein - 1 month ago 26
Java Question

Pascal's triangle faulty output

Hi I'm making an iterative Pascal's triangle in Java. So far everything works great, until number of rows exceed 13. The output becomes faulty. I must be doing something wrong here, please help.

IterativePascal:

public class IterativePascal extends ErrorPascal implements Pascal {
private int n;
IterativePascal(int n) throws Exception {
super(n);
this.n = n;
}
public void printPascal() {
printPascal(false);
}

public void printPascal(boolean upsideDown) {
if (n == 0) { return; }
for (int j = 0; j <= n; j++) {
for (int i = 0; i < j; i++) {
System.out.print(binom(j - 1, i) + (j == i + 1 ? "\n" : " "));
}
}
}

public long binom(int n, int k) {
return (k == 0 || n == k) ? 1 : faculty(n) / (faculty(k) * faculty(n - k));
}

private long faculty(int n) {
if (n == 0 || n == 1) { return 1; }
int result = 1;
for (int i = 2; i <= n; i++) {
result = result * i;
}
return result;
}
}


Output:

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
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 4 24 88 221 399 532 532 399 221 88 24 4 1 <----- wrong
1 0 1 5 14 29 44 50 44 29 14 5 1 0 1 <----- wrong


Help would be appriciated, since I'm new with algorithms.

Answer

You're reaching number overflow. Because 14! is too big to fill in java long.

The solution will be to use + instead of !.

Keep your triangle as an 2D array and iterate through it. Each cell should be sum of two 'above'.

+---+---+---+---+
| 1 |   |   |   |
| 1 | 1 |   |   |
| 1 | 2 | 1 |   |
| 1 | 3 | 3 | 1 |
+---+---+---+---+

The code will be as it follows:

public static void triangle(int n) {
    int[][] triangle = new int[n];
    for (int i = 0; i < n; i++) {
        triangle[i] = new int[i+1];
    }
    triangle[0][0] = 1;
    triangle[1][0] = 1;
    triangle[1][1] = 1;
    for (int i = 2; i < n; i++) {
        triangle[i][0] = 1;
        for (int j = 1; j < triangle[i].length - 1; j++) {
            triangle[i][j] = triangle[i-1][j] + triangle[i-1][j+1];
        }
        triangle[i][triangle[i].length-1] = 1;
    }
    printArray(triangle);
}

Edit:
As the OP requires recursive solution with binoms, I decided to add solution introducing BigIntegers as it might be the case.

public BigInteger binom(int n, int k) {
        return (k == 0 || n == k) ? BigInteger.ONE : faculty(n).divide((faculty(k).multiple(faculty(n - k)));
    }

private BigInteger faculty(int n) {
    BigInteger result = BigInteger.ONE;
    while (!n.equals(BigInteger.ZERO)) {
        result = result.multiply(n);
        n = n.subtract(BigInteger.ONE);
    }
    return result;
}

public void printPascal(boolean upsideDown) {
    if (n == 0) { return; }
    for (int j = 0; j <= n; j++) {
        for (int i = 0; i < j; i++) {
            System.out.print(binom(j - 1, i).toString() + (j == i + 1 ? "\n" : " "));
        }
    }
}