Pascal’s Triangle

December 6, 2011

We begin with the main program:

(define (pascal n)
  (let loop ((n n) (tri (list (list 1))))
    (if (zero? n)
        (reverse tri)
        (loop (- n 1)
          (cons (append (list 1)
                        (sums (car tri))
                        (list 1))
                tri)))))

This function builds up the triangle by row, sandwiching the two outer 1s around the sums of the prior row. Note that n+1 rows are calculated, because by convention the first row of Pascal’s Triangle is row zero. The sums are calculated in an auxiliary function:

(define (sums xs)
  (let loop ((xs xs) (zs (list)))
    (if (null? (cdr xs))
        (reverse zs)
        (loop (cdr xs)
              (cons (+ (car xs) (cadr xs)) zs)))))

The following function displays the triangle neatly, centering each row in width characters by pre-computing the string representation of the row:

(define (display-pascal width tri)
  (let loop ((tri tri))
    (when (pair? tri)
      (let* ((str (string-join #\space (map number->string (car tri))))
             (len (string-length str)))
        (display (make-string (quotient (- width len) 2) #\space))
        (display str)
        (newline))
      (loop (cdr tri)))))

Here are the first 11 rows of the triangle:

> (display-pascal 35 (pascal 10))
                 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

We used string-join from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/Qb5pOMrj.

If all you want to know is the number at a particular location in the triangle, without computing the entire triangle, the function choose computes the binomial coefficient:

(define (choose n k)
  (if (zero? k) 1
    (* n (/ k) (choose (- n 1) (- k 1)))))

For instance, (choose 8 6) = 28, which is the 6th item (counting from zero) in the 8th row (counting from zero). The function is called choose because, in the study of probability, it is the number of ways to choose k items from a population of n items.

About these ads

Pages: 1 2

24 Responses to “Pascal’s Triangle”

  1. […] today’s Programming Praxis our task is to neatly display Pascal’s triangle. Let’s get started, […]

  2. My Haskell solution (see http://bonsaicode.wordpress.com/2011/12/06/programming-praxis-pascals-triangle/ for a version with comments):

    import Text.Printf
    
    pascal :: [[Integer]]
    pascal = iterate (\prev -> 1 : zipWith (+) prev (tail prev) ++ [1]) [1]
    
    prettyPascal :: Int -> IO ()
    prettyPascal n = mapM_ (\r -> printf "%*s\n" (div (longest + length r) 2) r) rows
        where rows = map (unwords . map show) $ take (n + 1) pascal
              longest = length $ last rows
    
  3. Graham said

    My Python solution includes a function that uses binomial coefficients; while probably less efficient for small portions of the triangle, it could be modified to give a specific row without having to construct all the previous rows. My first solution would probably be more efficient/Python-acceptable if I used the extend method rather than the overloaded plus operator, but I think it would look uglier.

    from pprint import pprint
    from operator import mul
    
    def pascal(n):
        tri = [1]
        for _ in xrange(n + 1):
            yield tri
            tri = [1] + map(sum, zip(tri, tri[1:] + [0]))
    
    def binomial(a, b):
        return (reduce(mul, xrange(a - b + 1, a + 1), 1) //
                reduce(mul, xrange(1, b + 1), 1))
    
    def pascal_binom(n):
        for a in xrange(n + 1):
            yield [binomial(a, b) for b in xrange(a + 1)]
    
    if __name__ == "__main__":
        pprint(list(pascal(10)))
        pprint(list(pascal_binom(10)))
    
  4. Graham said

    Apologies for not padding the output appropriately (i.e. my triangle is left-aligned); for some reason the code and output here doesn’t look formatted on my sad little laptop, so I didn’t catch that we wanted the output centered. If I have time today, I’ll modify my solution.

  5. kawas said

    Clojure version similar to the Haskell version above
    too bad java’s printf does not support “*” as format width

    (defn trig-seq []
      (iterate #(concat [1] (map + % (next %)) [1]) '(1)))
    
    (defn lst->str [lst]
      (apply str (interpose " " lst)))
    
    (defn pretty-trig [n]
      (let [trigs (take (inc n) (trig-seq))
            longest (count (lst->str (last trigs)))]
        (doseq [x trigs]
          (let [xstr (lst->str x)
                width (quot (+ longest (count xstr)) 2)]
            (printf (str "%" width "s%n") xstr)))))
    
    (pretty-trig 10)
    
  6. Graham said

    Here’s a modified Python version, with a properly centered triangle:

    def pascal(n):
        tri = [1]
        for _ in xrange(n + 1):
            yield tri
            tri = [1] + map(sum, zip(tri, tri[1:] + [0]))
    
    def pretty_pascal(n):
        str_tris = ['  '.join(str(t) for t in tri) for tri in pascal(n)]
        width = len(str_tris[-1])
        for st in str_tris:
            diff = width - len(st)
            print ' ' * (diff // 2), st, ' ' * (diff // 2)
        return None
    
    if __name__ == "__main__":
        pretty_pascal(10)
    
  7. Erik said

    Emacs lisp version with an unbalanced triangle.
    The ‘pretty’ version just wraps the inner map call in a print, it’s not actually a balanced triangle.

    (defun pascal-val (x y)
      (cond ((= x 1) 1)
            ((= y 1) 1)
            ((> x y) 1)
            ((= x y) 1)
            (t (+ (pascal (- x 1) (- y 1))
                     (pascal x (- y 1))))))
    
    (defun in-range (start end)
      (cond
       ((= start end) `(,end))
       (t (cons start (in-range (+ 1 start) end)))))
    
    (defun pascal-triangle (y)
      (mapcar (lambda (y) 
                (mapcar (lambda (x) (pascal-val x y)) (in-range x y)))
              (in-range 1 y)))
    
    (defun pascal-triangle-pretty (y)
      (mapcar (lambda (y)
                (print (mapcar (lambda (x) (pascal-val x y)) (in-range x y))))
              (in-range 1 y)))
    
  8. Erik said

    I made a typo while fixing up my code for posting. It should work this time.

    (defun pascal-val (x y)
      (cond ((= x 1) 1)
            ((= y 1) 1)
            ((> x y) 1)
            ((= x y) 1)
            (t (+ (pascal-val (- x 1) (- y 1))
                     (pascal-val x (- y 1))))))
    
    (defun in-range (start end)
      (cond
       ((= start end) `(,end))
       (t (cons start (in-range (+ 1 start) end)))))
    
    (defun pascal-triangle (rows)
      (mapcar (lambda (y)
                (mapcar (lambda (x) (pascal-val x y)) (in-range 1 y)))
              (in-range 1 rows)))
    
    (defun pascal-triangle-pretty (rows)
      (mapcar (lambda (y)
                (print (mapcar (lambda (x) (pascal-val x y)) (in-range 1 y))))
              (in-range 1 rows)))
    
  9. Jussi Piitulainen said

    Pascal meets Pascal. Took me half an hour to install GNU Pascal and let Google refresh my memory this much.


    program pascal(output);
    var
       r, k : integer;

    function bc(r, k: integer) : integer;
    var
       j : integer;
       p : integer value 1;
    begin
       for j := 1 to k do
          p := p * (r - j + 1) div j;
       bc := p;
    end; { bc }

    begin
       for r := 0 to 10 do begin
          for k := 0 to r do begin
              write(bc(r, k), ' ');
          end;
          writeln;
       end;
    end.

    No centering. Just Pascal. Sorry. Here’s the 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

  10. Axio said

    I hadn’t written such ugly code for ages :)
    Any way, it’s quite efficient, and gives the indentation.

    ;; computes *half* of Pascal's triangle
    ;; Uses vectors for efficiency
    (define (pascal n)
      (case n
        ((1) (list (vector 1)))
        ((2) (list (vector 1 1) (vector 1)))
        (else
          (let* ((mox (ceiling (/ n 2)))
                 (now (make-vector mox))
                 (before (pascal (1- n)))
                 (last (car before)))
            (vector-set! now 0 1)
            ;; Basic recursive/dynamic programming
            (let loop ((i 1))
              (when (< i (1- mox))
                (vector-set! now i
                             (+ (vector-ref last (1- i))
                                (vector-ref last i)))
                (loop (1+ i))))
            ;; we've got an edge case when the middle of the line
            ;; has an odd length
            (vector-set! now (1- mox)
                         (+ (vector-ref last (1- (1- mox)))
                            (if (even? n)
                              (vector-ref last (1- mox))
                              (vector-ref last (1- (1- mox))))))
            (cons now before)))))
    
    ;; gives a list of indented strings that correspond to each
    ;; layer of Pascal's triangle.
    ;; the second line is an edge case making the case very ugly
    (define (p2str n)
      (let ((l (map
                 (lambda (v)
                   ;; Compose the two halves.
                   ;; We have two edge cases, wether the line has a "duplicate"
                   ;; middle value (i.e., even length)
                   ;; and wether this line is the second one
                   ;; (because I stored "1 1" already, not just "1")
                   (let* ((left (map number->string (vector->list v)))
                          (right (cond
                                   ((even? n)
                                    (if (= n 2)
                                      '()
                                      (reverse left)))
                                   (else (cdr (reverse left))))))
                     (set! n (1- n))
                     ;; stringify
                     (apply string-append (intersperce " "(append left right)))))
                 (pascal n))))
        (set! n (quotient (string-length (car l)) 2))
        (reverse
          (map
            (lambda (s)
              ;; indent.
              ;; That's a very ugly way to may a string of spaces :P
              (string-append
                (list->string (vector->list (make-vector (- n (quotient (string-length s) 2)) #\space)))
                s))
            l))))
    

    Output:

    > (p2str 10)                   
    ("             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")
    
  11. Axio said

    The same, naive:

    (define (pascal n)
      (if (= n 1) 
        (list (vector 1))
        (let* ((now (make-vector n 1))
               (before (pascal (1- n)))
               (last (car before)))
          (let loop ((i 1))
            (when (< i (1- n))
              (vector-set! now i
                           (if (zero? i)
                             1
                             (+ (vector-ref last i)
                                (vector-ref last (1- i)))))
              (loop (1+ i))))
          (cons now before))))
    
    (define (p2str n)
      (let ((l (map
                 (lambda (v)
                   (apply string-append
                          (intersperce " "
                                       (map number->string
                                            (vector->list v)) )))
                 (pascal n))))
        (set! n (quotient (string-length (car l)) 2))
        (reverse
          (map
            (lambda (s)
              (string-append
                (list->string (vector->list (make-vector (- n (quotient (string-length s) 2)) #\space)))
                s))
            l))))
    
  12. Xitami said

    code in C t
    [30
    ]={1}
    ;main(n
    ,k,a, b){
    puts("1 ");
    for(;n<10;n++
    ){for(b=k=0;k<=
    n;){a=t[k];t[k]=a
    +b;b=a;printf("%d "
    , t[k++]);}puts("");}
    }

  13. Xitami said

    t
    [30
    ]={1}
    ;main(n
    ,k,a, b){
    puts("1 ");
    for(;n<20;n++
    ){for(b=k=0;k<=
    n;){a=t[k];t[k]=a
    +b;b=a;printf("%d "
    ,t[k++]);}puts("");}}

  14. Siddharth said

    (define (maximum l)
    (define (m l x)
    (if (null? l) x
    (if (> (car l) x) (m (cdr l) (car l)) (m (cdr l) x))))
    (when (not (null? l)) (m (cdr l) (car l))))

    (define (map-n f n)
    (let loop ((i 0) (c ‘()))
    (if (string n)))
    (define (pad-number-within n ds)
    (cond ((= (count-digits n) ds) (number->string n))
    ((= (count-digits n) (- ds 1)) (string-append ” ” (number->string n)))
    (else (string-append ” ” (pad-number-within n (- ds 2)) ” “))))
    (define (pad-numbers-within ns ds) (map (lambda (a) (pad-number-within a ds)) ns))
    (define (pascal n)
    (let ((r ‘((1 1) (1))))
    (cond ((= n 1) (rest r))
    ((= n 2) r)
    (else
    (let loop ((r r) (c (- n 2)))
    (if (zero? c)
    r
    (loop (cons `(1 ,@(map + (cdar r) (car r)) 1) r) (- c 1))))))))
    (let* ((vals (pascal n))
    (max-pad (maximum (map count-digits (car vals))))
    (ms (make-spaces max-pad)))
    (let loop ((ps `(,(string-join ms (pad-numbers-within (car vals) max-pad))))
    (dcc (rest vals)))
    (if (null? dcc)
    (for-each (lambda (ss vs) (format #t “~a~a~%” ss vs))
    (map-n (lambda (i) (make-spaces (* max-pad (- (length vals) i 1))))
    (length ps))
    ps)
    (loop (cons (string-join ms (pad-numbers-within (car dcc) max-pad)) ps)
    (rest dcc))))))

    output:
    > (pretty-pascal 15)
    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
    #F
    >

    I’m not sure how to format it right for this post, but running the above code should produce correctly
    formatted output.

  15. Siddharth said

    oops! screwed up the code there..
    Hopefully, this should work

    (define (map-n f n)
     (let loop ((i 0) (c '()))
      (if (< i n) (loop (+ i 1) (cons (f i) c)) (reverse c))))
    
    (define (maximum l)
     (define (m l x)
      (if (null? l) x
          (if (> (car l) x) (m (cdr l) (car l)) (m (cdr l) x))))
     (when (not (null? l)) (m (cdr l) (car l))))
    
    (define (string-join delim l)
     (if (null? l) "" (foldl (lambda (a b) (string-append a delim b)) (cdr l) (car l))))
    
    (define (foldl f l i)
     (let loop ((l l) (c i)) (if (null? l) c (loop (rest l) (f c (first l))))))
    
    (define (pretty-pascal n)
     (define (make-spaces n) (string-join "" (map-n (lambda (_) " ") n)))
     (define (count-digits n) (string-length (number->string n)))
     (define (pad-number-within n ds)
      (cond ((= (count-digits n) ds) (number->string n))
    	((= (count-digits n) (- ds 1)) (string-append " " (number->string n)))
    	(else (string-append " " (pad-number-within n (- ds 2)) " "))))
     (define (pad-numbers-within ns ds) (map (lambda (a) (pad-number-within a ds)) ns))
     (define (pascal n)
      (let ((r '((1 1) (1))))
       (cond ((= n 1) (rest r))
    	 ((= n 2) r)
    	 (else
    	  (let loop ((r r) (c (- n 2)))
    	   (if (zero? c)
    	       r
    	       (loop (cons `(1 ,@(map + (cdar r) (car r)) 1) r) (- c 1))))))))
     (let* ((vals (pascal n))
    	(max-pad (maximum (map count-digits (car vals))))
    	(ms (make-spaces max-pad)))
      (let loop ((ps `(,(string-join ms (pad-numbers-within (car vals) max-pad))))
    	     (dcc (rest vals)))
       (if (null? dcc)
           (for-each (lambda (ss vs) (format #t "~a~a~%" ss vs))
    		 (map-n (lambda (i) (make-spaces (* max-pad (- (length vals) i 1))))
    			(length ps))
    		 ps)
           (loop (cons (string-join ms (pad-numbers-within (car dcc) max-pad)) ps)
    	     (rest dcc))))))
    

    Output:

    > (pretty-pascal 15)
                                                              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 
    #F
    > 
    
  16. Siddharth said

    Just realised that (pascal n) was unnecessary complex.
    It works just fine as:

    (define (pascal n)
      (let loop ((r '((1))) (c (- n 1)))
       (if (zero? c) r (loop (cons `(1 ,@(map + (cdar r) (car r)) 1) r) (- c 1)))))
    

    .. that brings the main chunk of code down to 23 lines :)

  17. Baher Nicola said

    int main( int argc, char** argv )
    {
    unsigned int arrayLength = 15;
    const unsigned int arraySize = 100;

    unsigned int data[arraySize][arraySize];
    memset(data, 0, arraySize * arraySize);
    for (int i = 0; i< arraySize; i++)
    {
    data[i][0] = 1;
    data[i][i] = 1;
    }

    unsigned int length = 1;
    while (length < arrayLength)
    {
    for (int i = 2; i < length; i++)
    {
    for (int j = 0; j < i; j++)
    {
    data[i][j] = data[i – 1][j – 1] + data[i – 1][j];
    }
    }

    length++;
    }

    for (int i = 0; i < arrayLength – 1; i++)
    {
    for (int h = 0; h < arrayLength – i; h++)
    printf(" ");
    for ( int j = 0; j < i + 1 ; j++)
    {
    printf("%d ", data[i][j]);
    }
    printf("\n");
    }
    }

  18. […] looking for some simple coding challenges recently, and discovered about Pascal’s triangle (here), and I’ve tried to generate one myself in C/Objective-C. For those that don’t know […]

  19. Paul Oldridge said
    #include <stdlib.h>
    #include <stdio.h>
    
    unsigned int * pascal_step(unsigned int * x, unsigned int n){
    	unsigned int * y = malloc(sizeof(unsigned int)*(n + 1)), i;
    		*y = y[n-1] = 1;
    	for(i = 1; i < n; i++)
    		y[i] = x[i] + x[i-1];
    	free(x);
    	return y;
    }
    
    void pascal(unsigned int height){
    	unsigned int * x = malloc(sizeof(unsigned int)), i, j, max_val, max_width;
    
    	for(max_val = i = height - 1; --i > height/2 && (max_val *= i););
    	for(i -= ~height & 1; i && (max_val /= i--););
    	for(max_width = 1; max_val /= 10; max_width++);
    
    	for(*x = 1, i = 1; i <= height + 1; i++){
    		printf("%*s", max_width*(height + 1 - i), "");
    		for(x = pascal_step(x, i), j = 0; j < i; j++)
    			printf("%-*u%*s", max_width, x[j], max_width, "");
    		printf("\n");
    	}
    	free(x);
    }
    
    int main(int argc, char * argv[]){
    	pascal(argc > 1 ? atoi(argv[1]) : 0);
    }
    
  20. Oops, that was before I finished editing it so that height 0 means a triangle with one row. Just remove the “~” from line 17 to make it work correctly:

    #include <stdlib.h>
    #include <stdio.h>
    
    unsigned int * pascal_step(unsigned int * x, unsigned int n){
    	unsigned int * y = malloc(sizeof(unsigned int)*(n + 1)), i;
    		*y = y[n-1] = 1;
    	for(i = 1; i < n; i++)
    		y[i] = x[i] + x[i-1];
    	free(x);
    	return y;
    }
    
    void pascal(unsigned int height){
    	unsigned int * x = malloc(sizeof(unsigned int)), i, j, max_val, max_width;
    
    	for(max_val = i = height - 1; --i > height/2 && (max_val *= i););
    	for(i -= height & 1; i && (max_val /= i--););
    	for(max_width = 1; max_val /= 10; max_width++);
    
    	for(*x = 1, i = 1; i <= height + 1; i++){
    		printf("%*s", max_width*(height + 1 - i), "");
    		for(x = pascal_step(x, i), j = 0; j < i; j++)
    			printf("%-*u%*s", max_width, x[j], max_width, "");
    		printf("\n");
    	}
    	free(x);
    }
    
    int main(int argc, char * argv[]){
    	pascal(argc > 1 ? atoi(argv[1]) : 0);
    }
    

    Output:

    ./a.out 13
                                                        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       

  21.                                                     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
    
  22. There, that’s how it actually looks haha. :)

  23. #include
    #define max 100

    int main()
    {
    int arr[max][max], n, i, j;
    for(i=0;i<=(max-1);i++)
    {
    for(j=0;j<=(max-1);j++)
    {
    arr[i][j]=0;
    }
    }
    printf("Enter the number of rows till which to compute: -\n");
    scanf("%d", &n);
    arr[0][n+1]=1;
    for(i=0;i<=n;i++)
    {
    for(j=0;j<=(n+1);j++)
    {
    arr[i+1][j]=arr[i][j]+arr[i][j+1];
    }
    }
    for(i=0;i<=n;i++)
    {
    for(j=0;j<=n+1;j++)
    {
    printf(" %d", arr[i][j]);
    }
    printf("\n\n");
    }
    return 0;
    }

  24. abed said

    hey guys i need your help, i need to display pascal’s triangle using Methods and for loops,check out the steps and please help me with this :
    i. Write a method public static long factorial(int n) that calculates the factorial of a numbers n.

    ii. Write a method public static long combination(int n, int k) that calculates the combination of k from n.

    iii. Write a method public static void pascal(int n) that outputs the triangle depending on n:
    a. Use printf to format the coefficients with a field of 4. The space in between adjacent coefficients is equivalent to 4 space characters.
    b. Relate the number of lines to the number n.
    c. Relate number of coefficients in each line to the line number.
    d. Relate the leading spaces (spaces printed at the beginning of each line) in each line to the line number.

    iv. Write a main method to output the pascal triangle of order n where n is read from the user

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: