[Exercise] Pascal's triangle

Joe

Write a function that print the n first lines of a Pascal triangle.

Joe

Simple recursion in python:

#!/usr/bin/python

def value (row, index):
    if index == 0 or index == row:
        return 1

    if index < 0 or index > row + 1:
        return 0

    return value (row-1, index) + value (row-1, index-1)

for i in range(10):
    print [value (i, x) for x in range(i+1)]

Output

$ code/pascal.py 
[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]

mesa177

Matlab/Octaviz:

function pascal_index = pascal_triangle(row)

switch nargin
    case 0
        error('This function acquires one input argument of type natural scalar.');
    case 1
        if (isscalar(row)&&isnumeric(row)&&(row>=0))
           if ~isequal(int8(row),row)
               fprintf('Intput is not a natural number.\n');
               fprintf('It is converted to: %d \n\n',int8(row)); 
           end
           disp(horzcat('The entires on Pascal triangle until the',' ',...
                        num2str(int8(row)),'th row is:'));
        else
            error('This function acquires an input of type natural scalar.');
        end
    otherwise
        error('Too many input arguments.');
end
pascal_index = {}; % Reserves the values of the entries on Pascal's triangle
for i = 1:row+1
    pascal_index{i} = [];
    for j = 1:i
        pascal_index{i}(j) = factorial(i-1)/(factorial(j-1)*factorial(i-j));
    end
    disp(pascal_index{i});
end
fprintf('\n');

Examples:

>> pascal_mag = pascal_triangle(10);
The entires on Pascal triangle until the 10th row is:
     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


>> pascal_mag2 = pascal_triangle();
??? Error using ==> pascal_triangle at 5
This function acquires one input argument of type natural scalar.
 
>> pascal_mag3 = pascal_triangle(11,14,15);
??? Error using ==> pascal_triangle
Too many input arguments.
 
>> pascal_mag4 = pascal_triangle(11.2);
Intput is not a natural number.
It is converted to: 11 

The entires on Pascal triangle until the 11th row is:
     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


>> pascal_mag5 = pascal_triangle('a');
??? Error using ==> pascal_triangle at 15
This function acquires an input of type natural scalar.

geek

Table[Binomial[n, r], {n, 0, 10}, {r, 0, n}]

saeidw

Geek, your solution prompted me to do some research about the binomial theorem and binomial coefficients. I decided to use this formula in my solution.

Here it is in Haskell:

n `choose` k = 
    let term n k i = (fromIntegral (n - (k - i))) / (fromIntegral i)
    in  truncate $ foldl (*) 1 (map (term n k) [1..k])

triangle n =
    let row n = map (choose n) [0..n]
    in  map (row) [0..n]

Sample run:

*Main> triangle 3
[[1],[1,1],[1,2,1],[1,3,3,1]]

geek

nice! it feels warm seeing some folds and maps. note that the way we're building the triangle is far from efficient, we should use instead the recursive formulation that rahmu implemented:

pascal :: Integer -> [[Integer]]
pascal 0 = [[1]]
pascal n = xs ++ [next_row (last xs)] where xs = pascal (n - 1)

next_row :: [Integer] -> [Integer]
next_row xs = [1] ++ zipWith (+) (init xs) (tail xs) ++ [1]

arithma

I am ripe for a haskell workshop. I'll be in the audience though.

raja

Well, here's my contribution. It's in python(as is usual for me). My solution essentially builds the triangle up from the ground up(instead of the more common recursive approach). The heart of the algorithm is the next_row function which, given a row computes the next one. I include both a documented and verbose answer as well as a 3-liner called compact_next_row() :D

def pascal_idx(n):
    """
    In the pascal triangle the value at the (n,m) is the sum of
    (n-1,m) and (n-1,m-1) (where n is the row and m is the column)

    This function generates a sequence given the current row in the
    triangle of the indices in the previous row which should be added

    Examples:

    >>> list(pascal_idx(1))
    [(0,), (0,)]

    This means that row 1(the 2nd row) should obtain it's first and
    second elements by copying the first element of row 0.

    >>> list(pascal_idx(2)) [(0,), (0, 1), (1,)]

    Row 2(the 3rd row) should obtain its first element by copying
    element 0 from row 1, its second element by summing elements 0 and
    1 in row 1 and its last element by copying element 1 from row 1

    One last example:
    >>> list(pascal_idx(3))
    [(0,), (0, 1), (1, 2), (2,)]
    """
    yield (0,)
    for i in range(1,n):
        yield i-1,i
    yield (n-1,)

def sum_of_indices(l, indices):
    """
    Calculates the sum of the elements in l pointed to by the indices
    """
    s = 0
    for i in indices:
        s += l[i]
    return s

def next_row(row):
    """
    Calculates the next row given a row of the pascal triangle. It
    invokes pascal_idx to know how to build the row and then performs
    the necessary sums
    """
    result = []
    for indices in pascal_idx(len(row)):
        result.append(sum_of_indices(row, indices))
    return result

def compact_next_row(row):
    soi = lambda l,indices: sum(map(lambda a:l[a], indices))
    indices = [(0,)] + [(i-1,i) for i in range(1, len(row))] + [(len(row)-1,)]
    return [soi(row, i) for i in indices]

if __name__ == "__main__":
    """
    A small example
    """
    print "The usual way:"
    row = [1]
    for i in range(10):
        print ",".join(map(str, row))
        row = next_row(row)

    print "\nNow to try out the compact way:"
    row = [1]
    for i in range(10):
        print ",".join(map(str, row))
        row = compact_next_row(row)

Result:

$ python pascal.py 
The usual way:
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

Now to try out the compact way:
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

NuclearVision

#Python:
from math import *
def pline(n):
        line = []
        for i in xrange(0,n+1):
            line.append(factorial(n)/(factorial(i)*factorial(n-i)))
        return ' '.join(map(str, line))
def pascal_lines(nth):
        for i in xrange(0,nth+1):
                print pline(i)

Ayman

Just started with C++ today, and that would be my first less trivial exercise

#include <iostream>
#include <vector>

using namespace std;

vector<int> consecutiveSum(vector<int> arr);
void printLine(vector<int> arr);
void printPascal(int n);

int main()
{
    printPascal(10); 

    return 0;
}

void printPascal(int n)
{
    vector<int> preSet = vector<int>();
    preSet.push_back(1); 
    
    for(int i = 0; i < n; i++)
    {
        printLine(preSet);

        vector<int> result = consecutiveSum(preSet);

        preSet = result; 

        preSet.insert(preSet.begin(),1);
        preSet.push_back(1);
    }
}

vector<int> consecutiveSum(vector<int> arr)
{
    vector<int> summed = vector<int>();

    for(int i = 0; i < (arr.size() - 1); i++)
    {
        summed.push_back(arr[i] + arr[i+1]);
    }

    return summed;
}

void printLine(vector<int> vect)
{
    vector<int>::iterator it;

    for(it = vect.begin(); it < vect.end(); it++)
    {
        cout << *it << " ";
    }

    cout << "\n";
}

The solution is simply on each iteration take the previously generated row, sum the consecutive pairs in the list, append and pre-pend to the list 1, current row becomes the old row for the next iteration, and so forth...

NuclearVision

from math import factorial as f;
N=10
for j in xrange(0,N+1):print ",".join([str(f(j)/(f(i)*f(j-i))) for i in xrange(0,j+1)])

NuclearVision

#include <iostream>
using namespace std;
long long unsigned f(int n)
{ if(n==0) return 1;
  long long unsigned j=1llu;
  for(n;n>1;n--)
  { j*=n;
  }
 return j;
}
 
void lineout( int n)
{ int j=-1;
  while(j<n)
  {  j++;
     cout<<f(n)/(f(j)*f(n-j))<<" ";
  }
  cout<<endl;
}
void triangleout(int n)
{ int k=0;
  for(k;k<=n;k++)
  {  lineout(k);
  }
}
     
int main(void)
{ int i=5;//number of lines
 triangleout(i);
 return 0;
}

Overflow causes issues for lightly big numbers, depends on your machine. I'll be going into overflow deeper when I have time.
Any feedback for improving code is appreciated : ]

Joe

Still working on Go

package main

import (
	"fmt"
	"log"
	"os"
	"strconv"
)

func PascalTriangle(n int) {
	for i := 0; i <= n; i++ {
		for j := 0; j <= i; j++ {
			fmt.Printf("%d\t", PascalValue(j, i))
		}
		fmt.Printf("\n")
	}
}

func PascalValue(i int, j int) int {
	if i == 0 || i == j {
		return 1
	}
	return PascalValue(i-1, j-1) + PascalValue(i, j-1)
}

func main() {
	if len(os.Args) > 2 {
		log.Fatal("Wrong number of CLI arguments.")
	}

	n, err := strconv.Atoi(os.Args[1])
	if err != nil {
		log.Fatal(err)
	}
	PascalTriangle(n)
}