A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Joe****Member**

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

**Joe****Member**

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****Member**

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

**geek****Member**

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

**saeidw****Member**

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

*Last edited by saeidw (January 9 2012)*

**geek****Member**

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

*Last edited by geek (January 9 2012)*

**arithma****Member**

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

**raja****Member**

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 = [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****Member**

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

**Ayman****Member**

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****Member**

```
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****Member**

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

**Joe****Member**

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

Pages: **1**