Pascal's Triangle

Pascal's triangle has a lot of mathematically interesting properties; It represents binomial coefficients (n choose k or combination of a set), you can find within it the powers of 2, the powers of 11, the Fibonacci sequence, Sierpinski's triangle (a fractal), all the figurate numbers, Mersenne numbers and Catalan numbers, just to name a few. Furthermore, generating Pascal's triangle is quite simple, requiring only addition. Sometimes in mathematics something is both profound AND simple to understand. Such is the case with Pascal's triangle.

Recently, I made a contribution to rosettacode.org. If you have not checked out rosettacode.org before, you should definitely do so. I made a contribution to the Pascal's triangle task for the C# language. You can check it out here, or you can just view the code below.

My version of Pascal's Triangle is short, succinct, uses the BigInteger class for arbitrarily large numbers, and uses the algorithm to generate a single row of Pascal's triangle without needing to generate every row before it. This was originally the use case for writing this code in the first place; I wanted to generate high-numbered rows in a computationally feasible way. What does row # 5000 look like, for example? Well, could use the code below and generate the 5000th row of Pascal's triangle and format it as a string with the following one-liner: `string result = string.Join(" ", PascalsTriangle.GetRow(5000).Select(n => n.ToString()));`. You can also, of course, generate actual triangle-shaped rows of numbers:

                                                           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    13    78    286   715  1287  1716  1716  1287   715   286   78    13     1                    
                 1    14    91    364  1001  2002  3003  3432  3003  2002  1001   364   91    14     1                 
              1    15    105   455  1365  3003  5005  6435  6435  5005  3003  1365   455   105   15     1              
           1    16    120   560  1820  4368  8008  11440 12870 11440 8008  4368  1820   560   120   16     1           
        1    17    136   680  2380  6188  12376 19448 24310 24310 19448 12376 6188  2380   680   136   17     1        
     1    18    153   816  3060  8568  18564 31824 43758 48620 43758 31824 18564 8568  3060   816   153   18     1     
  1    19    171   969  3876  11628 27132 50388 75582 92378 92378 75582 50388 27132 11628 3876   969   171   19     1  

Awww, yes... that's pleasing.

Much of the pleasing effect is due to the CenterString(string, int) method (below).



And the code to do all that is thus:

public static class PascalsTriangle
{  
 public static IEnumerable GetTriangle(int quantityOfRows)
 {
  IEnumerable range = Enumerable.Range(0, quantityOfRows).Select(num => new BigInteger(num));
  return range.Select(num => GetRow(num).ToArray());
 }

 public static IEnumerable GetRow(BigInteger rowNumber)
 {
  BigInteger denominator = 1;
  BigInteger numerator = rowNumber;

  BigInteger currentValue = 1;
  for (BigInteger counter = 0; counter <= rowNumber; counter++)
  {
   yield return currentValue;
   currentValue = BigInteger.Multiply(currentValue, numerator--);
   currentValue = BigInteger.Divide(currentValue, denominator++);
  }
  yield break;
 }

 public static string FormatTriangleString(IEnumerable triangle)
 {
  int maxDigitWidth = triangle.Last().Max().ToString().Length;
  IEnumerable rows = triangle.Select(arr =>
    string.Join(" ", arr.Select(array => CenterString(array.ToString(), maxDigitWidth)) )
  );
  int maxRowWidth = rows.Last().Length;
  return string.Join(Environment.NewLine, rows.Select(row => CenterString(row, maxRowWidth)));
 }

 private static string CenterString(string text, int width)
 {
  int spaces = width - text.Length;
  int padLeft = (spaces / 2) + text.Length;
  return text.PadLeft(padLeft).PadRight(width);
 }
}

Note: This requires the System.Numerics library.

I make liberal use of Linq to keep the code short, yet expressive.

The code that generated the Pascal's triangle above, is:

IEnumerable triangle = PascalsTriangle.GetTriangle(20);
string output = PascalsTriangle.FormatTriangleString(triangle)
Console.WriteLine(output);

Other, arbitrarily large, number types available include the BigDecimal class, the BigComplex class, and the BigRational class. They are all available on my GitHub.


Thanks for stopping by!