pascal's Triangle implementation

Question

I am trying to make a program for pascal's triangle,the formaula to calculate the rth value in nth row is n!/r!(n-r)!

I've been tring to implement it like this:

          #include <iostream>     // std::cout, std::endl
          #include <iomanip>      // std::setw
          int Pascal(int ,int );
          int Factorial( int);
          int main () 
          {
           int n=0;//Number of rows in the triangle
           for(int i=12;i>0;i--)
            {
              std::cout << std::setw(i)<<std::endl;
              for (int j=1;j<12-i;j++)
               {
                int r=0; //rth element initialized for each row
                int P= Pascal(r,n);
                std::cout << P ;
                std::cout <<std::setw(2);
                r=r+1;
               }

              n=n+1;

           }
               std::cout<<std::endl;
                   return 0;
           }
           int Pascal(int r,int n)
           {
               int d = n-r; ///Difference of n with r
               int f1; ///factorial of n
               int f2; ///factorial of r
               int f3; ///factorial of (n-r)

               f1=Factorial(n);
               f2=Factorial(r);
               f3=Factorial(d);
               return f1/(f2*f3);

           }
           int Factorial( int begin )
           {
                   int F;
                   if ( begin == 0 )
                   {
                    return 1; 
                   }
                   else
                   {
                     F= begin*Factorial(begin-1);
                   }
              return F;         
             }

but somehow I am getting this output:

                   1
                  1 1
                 1 1 1
                1 1 1 1
               1 1 1 1 1
              1 1 1 1 1 1
             1 1 1 1 1 1 1
            1 1 1 1 1 1 1 1
           1 1 1 1 1 1 1 1 1
          1 1 1 1 1 1 1 1 1 112

Could someone guide me where am I going wrong?

Answer 1

Your first, obvious problem is of course that you should be printing Pascal(i,j). Your second is more subtle:

Recursion

The whole point of Pascal's Triangle is that it gives a way of computing binomial coefficients without needing to compute the factorials.

The problem is factorials grow really quickly and a coefficient such as Pascal(1,120) = 120!/(1!*119!}, is equal only to 120, but its nominator and denominator are on the order of 10^198 which could not be stored in any machine integer type.

Check out Pascal's Triangle on Wikipedia. The whole point is the recursive relation:

Pascal( r, n ) = Pascal( r-1, n-1 ) + Pascal( r, n-1 )

Here's a simple solution making use of that (this only prints the r,n pascal number):

#include <iostream>
#include <sstream>

int pascal( int r, int n ) {
    if( n == 0 )
        return 1;

    if( r == 0 || r == n )
        return 1;

    return pascal( r - 1, n - 1 ) + pascal( r, n - 1 );
}

int main( int argc, char *argv[] ) {
    if( argc != 3 ) {
        std::cout << "Expected exactly 3 arguments." << std::endl;
        return -1;
    }

    int r, n;

    std::stringstream ss;
    ss << argv[1] << ' ' << argv[2];
    ss >> r >> n;

    if( ss.bad() || r < 0 || n < 0 || r > n ) {
        std::cout << "Invalid argument values." << std::endl;
        return -2;
    }

    std::cout << pascal( r, n ) << std::endl;
    return 0;
}

Memoization

There is a third and even more subtle problem with this method, its complexity is much worse than it needs to be. Think about computing Pascal(3,6):

                       Pascal(3,6)                      =
=        Pascal(2,5)        +        Pascal(3,5)        =
= (Pascal(1,4)+Pascal(2,4)) + (Pascal(2,4)+Pascal(3,4)) = ...

In that last line you'll notice Pascal(2,4) appears twice which means your code will compute it twice. Futhermore Pascal( 3, 5 ) is actually equal to Pascal(2,5). So your could is computing Pascal(2,5) twice, which means computing Pascal(2,4) four times. This means as r and n grow large the program will be very slow. We would like to compute each Pascal(i,j) a single time and then save its value to be used by other calls. To do this, a simple way is to use a map which maps (r,n) pairs to Pascal(r,n) values: std::map< std::pair, int >. This method is called memoization. Also, changing ints to long long for big numbers, you get the following algorithm:

#include <iostream>
#include <sstream>
#include <map>

typedef long long                                          Integer;
typedef std::map< std::pair< Integer, Integer >, Integer > MemoMap;
typedef MemoMap::iterator                                  MemoIter;

MemoMap memo;

Integer pascal( Integer r, Integer n ) {
    // make sure r <= n/2 using the fact that pascal(r,n)==pascal(n-r,n)
    if( r > n / 2LL )
        r = n - r;

    // base cases
    if( n == 0LL || r == 0LL )
        return 1LL;

    // search our map for a precalculated value of pascal(r,n)
    MemoIter miter = memo.find( std::make_pair( r, n ) );

    // if it exists return the precalculated value
    if( miter != memo.end() )
        return miter->second;

    // otherwise run our function as before
    Integer result = pascal( r - 1LL, n - 1LL ) + pascal( r, n - 1LL );

    // save the value and return it
    memo.insert( std::make_pair( std::make_pair( r, n ), result ) );

    return result;
}

int main( int argc, char *argv[] ) {
    if( argc != 3 ) {
        std::cout << "Expected exactly 3 arguments." << std::endl;
        return -1;
    }

    Integer r, n;

    std::stringstream ss;
    ss << argv[ 1 ] << ' ' << argv[ 2 ];
    ss >> r >> n;

    if( ss.bad() || r < 0LL || n < 0LL || r > n ) {
        std::cout << "Invalid argument values." << std::endl;
        return -2;
    }

    std::cout << pascal( r, n ) << std::endl;

    return 0;
}

Before, Pascal(5,100) would never terminate. Now it finishes instantly on my computer. Integrate this code into yours and you'll be a happy panda.

Bottom-up

Memoization is top-down dynamic programming i.e. you first think of the hardest problem and then divide it into simpler, overlapping problems while saving the results along the way. A bottom up solution would start with the first row of the Pascal Triangle and keep computing following rows - this is more efficient, both in speed and memory (storing only two arrays). The top-down method however is easier to implement (you don't have to think about what values you're going to need you just save everything) and it allows you to save intermediate results between independent pascal() calls. In your case, since you're trying to print Pascal's Triangle by calling pascal independently many times, this is the appropriate method. If you print and compute at the same time, bottom up is by far the most efficient way of doing it:

#include <iostream>
#include <sstream>
#include <vector>


typedef long long Integer;

void print_pascal( Integer maxn ) {
    std::vector< Integer > prevRow, currentRow;

    prevRow.resize( maxn + 1 );
    currentRow.resize( maxn + 1);

    prevRow[ 0 ] = 1;
    // print first row.
    std::cout << 1 << std::endl;
    for( Integer currentN = 1 ; currentN <= maxn ; ++ currentN ) {
        // compute & print current row
        currentRow[ 0 ] = currentRow[ currentN ] = 1;
        std::cout << 1;
        for( Integer r = 1 ; r < currentN ; ++ r ) {
            currentRow[ r ] = prevRow[ r - 1 ] + prevRow[ r ];
            std::cout << ' ' << currentRow[ r ];
        }
        std::cout << ' ' << 1 << std::endl;

        // constant time because swap() only swaps internal ptrs.
        currentRow.swap( prevRow );
    }
}

int main( int argc, char *argv[] ) {
    if( argc != 2 ) {
        std::cout << "Expected exactly 1 argument." << std::endl;
        return -1;
    }

    Integer maxn;

    std::stringstream ss;
    ss << argv[ 1 ]; ss >> maxn;

    if( ss.bad() || maxn < 0LL ) {
        std::cout << "Invalid argument values." << std::endl;
        return -2;
    }

    print_pascal( maxn );

    return 0;
}

Answer 2

The very first thing you've gone wrong at is the formatting of your code. It's horrible. (Sorry, it really is.)

The second thing is that you are always printing Pascal(r, n) whereas they are constant 0, 0 - you should print Pascal(i, j) instead, since i and j are the loop counters.

By the way, you'd be better off calculating the factorials iteratively and using long enough integers, your code threw SIGXCPU on IDEOne and segfaulted on my computer.