/*
  Pascal
  written by Keith Fenske
  Saturday, 18 May 2002
  Copyright (c) 2002 by Keith Fenske.  All rights reserved.

  This Java program prints the first fifteen lines of Pascal's Triangle, as
  shown in question #25 on page 82 of "Discrete Mathematical Structures"
  (the CS 1303 textbook).

  There is no input from the user.  Each line in the triangle is converted
  into a string and centered in the output (to make the triangle pretty).
  Some of the program lines are flagged "step 2".  That is an intermediate
  step in the assignment to print the triangle without centering.
*/

public class Pascal
{
  static final int LINES = 15;    // number of triangle lines to print
  static final int WIDTH = 72;    // output width to center strings

  public static void main(String[] args)
  {
    int n;                        // number of objects (lines in triangle)
    int r;                        // how many objects we choose
    int spaces;                   // number of spaces to left of center
    String output;                // output string

    for (n = 0; n <= LINES; n ++)
    {
//    System.out.print(choose(n,0)); // output for step 2
      output = "" + choose(n,0);  // start output string
      for (r = 1; r <= n; r ++)
      {
//      System.out.print(" " + choose(n,r)); // output for step 2
        output = output + " " + choose(n,r); // append to output string
      }
//    System.out.println();       // output for step 2
      spaces = (WIDTH - output.length()) / 2; // number of spaces to center
      while (spaces > 0)
      {
        System.out.print(" ");    // print one space
        spaces --;                // decrement remaining spaces
      }
      System.out.println(output); // print output string
    }

  } // end of main()


/*
  choose() method

  This method implements the combination function (page 79) to calculate the
  number of combinations of n objects taken r at a time:

                   n!
  choose(n,r) = --------
                r!(n-r)!

  The factorial function grows very quickly, and anything over 20! exceeds
  the limits of a 64-bit long integer.  To improve the range of this method,
  we remove the larger of r! and (n-r)! from n! first.  This allows us to
  compute values up to n=29 for any r, 0 <= r <= n.
*/
  static long choose(int n, int r)
  {
    int i;                        // index variable in for loop
    int max, min;                 // maximum and minimum of r and (n-r)
    long result;                  // function result

    max = Math.max(r, n-r);       // larger term on bottom of equation
    min = Math.min(r, n-r);       // smaller term on bottom of equation

    result = 1;                   // initial value

    // only calculate the part of n! greater than max!

    for (i = n; i > max; i --)
      result = result * i;

    // remove min! from result

    for (i = min; i > 1; i --)
      result = result / i;

    return result;

  } // end of choose()

} // end of class