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.
Pages: 1 2
[…] today’s Programming Praxis our task is to neatly display Pascal’s triangle. Let’s get started, […]
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 rowsMy 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)))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.
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)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)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)))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)))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
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")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))))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("");}
}
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("");}}
(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.
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 >Just realised that (pascal n) was unnecessary complex.
It works just fine as:
.. that brings the main chunk of code down to 23 lines :)
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");
}
}
[…] 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 […]
#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); }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
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 1There, that’s how it actually looks haha. :)
#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;
}
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