Pascal's Triangle

From Rosetta Code

Pascal's triangle is an interesting math concept. Its first few rows look like this:

   1
  1 1
 1 2 1
1 3 3 1

where each element of each row is either 1 or the sum of the two elements right above it. For example, the next row would be 1 (since the first element of each row doesn't have two elements above it), 4 (1 + 3), 6 (3 + 3), 4 (3 + 1), and 1 (since the last element of each row doesn't have two elements above it). Each row n (starting with row 0 at the top) shows the coefficients of the binomial expansion of (x + y)ⁿ.

Write a function that prints out the first n rows of the triangle (with f(1) yielding the row consisting of only the element 1). This can be done either by summing elements from the previous rows or using a binary coefficient or combination function. Behavior for n <= 0 does not need to be uniform, but should be noted.

Contents 1 Ada 2 Common Lisp 3 D 4 Forth 5 Fortran 6 Haskell 7 J 7.1 solution 7.2 explanation 8 Java 8.1 Summing from Previous Rows 9 OCaml 10 Perl 11 Python 12 Ruby

[edit] Ada

 
-- Pascals triangle
 
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Text_Io; use Ada.Text_Io;
 
procedure Pascals_Triangle is
   type Row is array(Positive range <>) of Integer;
   type Row_Access is access Row;
   type Triangle is array(Positive range <>) of Row_Access;
   function General_Triangle(Depth : Positive) return Triangle is
      Result : Triangle(1..Depth);
   begin
      for I in Result'range loop
         Result(I) := new Row(1..I);
         for J in 1..I loop
            if J = Result(I)'First or else J = Result(I)'Last then
               Result(I)(J) := 1;
            else
               Result(I)(J) := Result(I - 1)(J - 1) + Result(I - 1)(J);
            end if; 
         end loop;
      end loop;
      return Result;
   end General_Triangle;
   procedure Print(Item : Triangle) is
   begin
      for I in Item'range loop
         for J in 1..I loop
            Put(Item => Item(I)(J), Width => 3);
         end loop;
         New_Line;
      end loop;
   end Print;
begin
   Print(General_Triangle(7));
end Pascals_Triangle;
 

[edit] Common Lisp

To evaluate, call (pascal n). For n < 1, it simply returns nil.

(defun pascal (n)
   (genrow n '(1)))

(defun genrow (n l)
   (if (< 0 n)
      (progn
         (print l)
         (genrow (- n 1) (cons 1 (newrow l))))))

(defun newrow (l)
   (if (> 2 (length l))
      '(1)
      (cons (+ (car l) (cadr l)) (newrow (cdr l)))))

[edit] D

There is similarity between Pascal's triangle and Sierpinski triangle. Their difference are the initial line and the operation that act on the line element to produce next line. The following is a generic pascal's triangle implementation for positive number of lines output (n).

import std.stdio, std.string, std.format : fmx = format ; 
 
string Pascal(alias dg, T, T initValue)(int n) {
  string output ;
  void append(T[] l) {
    output ~= repeat(" ", (n - l.length + 1)*2) ;
    foreach(e; l) output ~= fmx("%4s", fmx("%4s",e)) ;
    output ~= "\n" ;
  }
  if(n > 0) {
    T[][] lines = [[initValue]] ;
    append(lines[0]) ;
    for(int i = 1 ; i < n ; i++) {
      lines ~= lines[i-1] ~ initValue ; // length + 1
      for(int j = 1 ; j < lines[i-1].length ; j++)
        lines[i][j] = dg(lines[i-1][j], lines[i-1][j-1]) ;
      append(lines[i]) ;
    }
  }       
  return output ;
}
 
string delegate(int n) GenericPascal(alias dg, T, T initValue)(){
  mixin Pascal!(dg, T, initValue) ;
  return &Pascal ;
}
 
char xor(char a, char b) { return a == b ? '_' : '*' ; }
 
void main() {
  auto pascal     = GenericPascal!((int a, int b) { return a + b; }, int ,  1 ) ;
  auto sierpinski = GenericPascal!(xor, char, '*') ;
 
  foreach(i ; [1,5,9])  writef(pascal(i)) ;
  // an order 4 sierpinski triangle is a 2^4 lines generic pascal triangle with xor operation
  foreach(i ; [16]) writef(sierpinski(i)) ; 
}

[edit] Forth

: init ( n -- )
  here swap cells erase  1 here ! ;
: .line ( n -- )
  cr here swap 0 do dup @ . cell+ loop drop ;
: next ( n -- )
  here swap 1- cells here + do
    i @ i cell+ +!
  -1 cells +loop ;
: pascal ( n -- )
      dup init   1  .line
  1 ?do i next i 1+ .line loop ;

[edit] Fortran

Works with: Fortran version 90 and later

Prints nothing for n<=0. Output formatting breaks down for n>20

PROGRAM Pascals_Triangle

  CALL Print_Triangle(8)

END PROGRAM Pascals_Triangle

SUBROUTINE Print_Triangle(n)

  IMPLICIT NONE
  INTEGER, INTENT(IN) :: n
  INTEGER :: c, i, j, k, spaces

  DO i = 0, n-1
     c = 1
     spaces = 3 * (n - 1 - i)
     DO j = 1, spaces
        WRITE(*,"(A)", ADVANCE="NO") " "
     END DO
     DO k = 0, i
        WRITE(*,"(I6)", ADVANCE="NO") c
        c = c * (i - k) / (k + 1)
     END DO
     WRITE(*,*)
  END DO

END SUBROUTINE Print_Triangle

[edit] Haskell

An approach using the "think in whole lists" principle: Each row in the triangle can be calculated from the previous row by adding a shifted version of itself to it, keeping the ones at the ends. The Prelude function zipWith can be used to add two lists, but it won't keep the old values when one list is shorter. So we need a similar function

zapWith :: (a -> a -> a) -> [a] -> [a] -> [a]
zapWith f xs [] = xs
zapWith f [] ys = ys
zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys

Now we can shift a list and add it to itself, extending it by keeping the ends:

extendWith f [] = []
extendWith f xs@(x:ys) = x : zapWith f xs ys

And for the whole (infinite) triangle, we just iterate this operation, starting with the first row:

pascal = iterate (extendWith (+)) [1]

For the first n rows, we just take the first n elements from this list, as in

*Main> take 6 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]

[edit] J

[edit] solution

    !/~@i. N

[edit] explanation

Of course, the triangle itself is simply the table of number-of-combinations, for the first N non-negative integers.

That is, C(n,k) for all n,k ∈ [0 .. n). J's notation for C(n,k) is k ! n (mnemonic: combinations are closely related to factorials, which are denoted by ! in math).

So, for example, the number of ways to choose a poker hand (5 cards from the deck of 52):

   5!52     
 2598960

So ! is the mathematical choose function. What of /~@i.? Well, you can think of /~ as "table of" and @i. "the first N non-negative integers (i.e. 0 .. N-1)".

So, for example, here's the multiplication table you had to memorize in first grade:

    */~@i. 10
 0 0  0  0  0  0  0  0  0  0
 0 1  2  3  4  5  6  7  8  9
 0 2  4  6  8 10 12 14 16 18
 0 3  6  9 12 15 18 21 24 27
 0 4  8 12 16 20 24 28 32 36
 0 5 10 15 20 25 30 35 40 45
 0 6 12 18 24 30 36 42 48 54
 0 7 14 21 28 35 42 49 56 63
 0 8 16 24 32 40 48 56 64 72
 0 9 18 27 36 45 54 63 72 81

and here's the addition table for 0 to 4

   +/~@i. 4
0 1 2 3
1 2 3 4
2 3 4 5
3 4 5 6

Similarly, !/~@i. is the number-of-combinations table, or the "choose" table:

   !/~@i. 5
1 1 1 1 1
0 1 2 3 4
0 0 1 3 6
0 0 0 1 4
0 0 0 0 1

Of course, to format it nicely, you need to do a little more work:

    ([:'0'&=`(,:&' ')} -@|. |."_1 [: ":@|: !/~)@i. 5
     1    
    1 1   
   1 2 1  
  1 3 3 1 
 1 4 6 4 1

(I won't bother explaining the formatting.)

[edit] Java

[edit] Summing from Previous Rows

Works with: Java version 1.5+

This implementation prints nothing for n = 0.

import java.util.LinkedList;
...//class definition, etc.
public static void genPyrN(int rows){
	if(rows <= 0) return;
	//save the last row here
	LinkedList<Integer> last= new LinkedList<Integer>();
	last.add(1);//it's row 0...it starts with 1
	for(int i= 0;i <= rows;++i){
		//work on the next row
		LinkedList<Integer> thisRow= new LinkedList<Integer>();
		for(int j= 0;j < i;++j){//loop the number of elements in this row
			if(j == last.size() || j == 0){//if we're on the ends
				thisRow.add(1);
			}else{//otherwise, sum from the last row
				thisRow.add(last.get(j - 1) + last.get(j));
			}
		}
		thisRow.add(1);
		last= thisRow;//save this row
		System.out.println(thisRow);
	}
}

[edit] OCaml

(* generate next row from current row *)
let next_row row =
  List.map2 (+) ([0] @ row) (row @ [0])
 
(* returns the first n rows *)
let pascal n =
  let rec loop i row =
    if i = n then []
    else row :: loop (i+1) (next_row row)
  in loop 0 [1]

[edit] Perl

sub pascal
# Prints out $n rows of Pascal's triangle. It returns undef for
# failure and 1 for success.
  {my $n = shift;
   $n < 1 and return undef;
   print "1\n";
   $n == 1 and return 1;
   my @last = (1);
   foreach my $row (1 .. $n - 1)
      {my @this = map {$last[$_] + $last[$_ + 1]} 0 .. $row - 2;
       @last = (1, @this, 1);
       print join(' ', @last), "\n";}
   return 1;}

[edit] Python

def pascal(n):
   """Prints out n rows of Pascal's triangle.
 
   It returns False for failure and True for success."""
   if n < 1: return False
   print 1
   if n == 1: return True
   last = [1]
   for row in range(1, n):
       this = [last[i] + last[i + 1] for i in range(row - 1)]
       last = [1] + this + [1]
       print " ".join(map(str, last))
   return True

[edit] Ruby

 
def pascal(n = 1)
 
  return if n < 1
 
  # set up a new array of arrays with the first value
  p = [[1]]
 
  # for n - 1 number of times,
  (n - 1).times do |i|
 
    # inject a new array starting with [1]
    p << p[i].inject([1]) do |result, elem|
 
      # if we've reached the end, tack on a 1.
      # else, tack on current elem + previous elem
      if p[i].length == result.length
        result << 1
      else
        result << elem + p[i][result.length]
      end
    end
  end
 
  # and return the triangle.
  p
 
end