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.
[…] 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):
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.
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
Here’s a modified Python version, with a properly centered triangle:
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.
I made a typo while fixing up my code for posting. It should work this time.
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.
Output:
The same, naive:
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
Output:
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 […]
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:
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
There, 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