# LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

## #1 January 7 2012

Joe
Member ### [Exercise] Pascal's triangle

Write a function that print the n first lines of a Pascal triangle. ## #2 January 7 2012

Joe
Member ### Re: [Exercise] Pascal's triangle

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, 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]`````` ## #3 January 7 2012

mesa177
Member ### Re: [Exercise] Pascal's triangle

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.``````

Last edited by mesa177 (January 8 2012) ## #4 January 8 2012

geek
Member

### Re: [Exercise] Pascal's triangle

``Table[Binomial[n, r], {n, 0, 10}, {r, 0, n}]`` ## #5 January 9 2012

saeidw
Member

### Re: [Exercise] Pascal's triangle

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.

``````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,2,1],[1,3,3,1]]``````

Last edited by saeidw (January 9 2012) ## #6 January 9 2012

geek
Member

### Re: [Exercise] Pascal's triangle

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 = []
pascal n = xs ++ [next_row (last xs)] where xs = pascal (n - 1)

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

Last edited by geek (January 9 2012) ## #7 January 10 2012

arithma
Member ### Re: [Exercise] Pascal's triangle

I am ripe for a haskell workshop. I'll be in the audience though. ## #8 January 13 2012

raja
Member

### Re: [Exercise] Pascal's triangle

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()

``````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 = 
for i in range(10):
print ",".join(map(str, row))
row = next_row(row)

print "\nNow to try out the compact way:"
row = 
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`````` ## #9 August 1 2012

NuclearVision
Member ### Re: [Exercise] Pascal's triangle

``````#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)``````

Last edited by NuclearVision (April 20 2014) ## #10 November 9 2013

Ayman
Member ### Re: [Exercise] Pascal's triangle

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... ## #11 November 9 2013

NuclearVision
Member ### Re: [Exercise] Pascal's triangle

``````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)])`````` ## #12 April 20 2014

NuclearVision
Member ### Re: [Exercise] Pascal's triangle

``````#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 : ]

Last edited by NuclearVision (April 20 2014) ## #13 February 29 2016

Joe
Member ### Re: [Exercise] Pascal's triangle

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)
if err != nil {
log.Fatal(err)
}
PascalTriangle(n)
}`````` 