Write a function that print the n first lines of a Pascal triangle.
[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]
[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]
- Edited
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.
Table[Binomial[n, r], {n, 0, 10}, {r, 0, n}]
- Edited
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:
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]]
- Edited
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]
I am ripe for a haskell workshop. I'll be in the audience though.
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
7 months later
- Edited
#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)
a year later
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...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)])
5 months later
- Edited
#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 : ]
2 years later
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)
}