Pascal matrix generation: Difference between revisions
(→{{header|Ruby}}: add binomial coefficient) |
(Tcl implementation added) |
||
| Line 548: | Line 548: | ||
[1, 4, 10, 20, 35], |
[1, 4, 10, 20, 35], |
||
[1, 5, 15, 35, 70]] |
[1, 5, 15, 35, 70]] |
||
</pre> |
|||
=={{header|Tcl}}== |
|||
<lang Tcl> |
|||
package require math |
|||
namespace eval pascal { |
|||
proc upper {n} { |
|||
for {set i 0} {$i < $n} {incr i} { |
|||
for {set j 0} {$j < $n} {incr j} { |
|||
puts -nonewline \t[::math::choose $j $i] |
|||
} |
|||
puts "" |
|||
} |
|||
} |
|||
proc lower {n} { |
|||
for {set i 0} {$i < $n} {incr i} { |
|||
for {set j 0} {$j < $n} {incr j} { |
|||
puts -nonewline \t[::math::choose $i $j] |
|||
} |
|||
puts "" |
|||
} |
|||
} |
|||
proc symmetric {n} { |
|||
for {set i 0} {$i < $n} {incr i} { |
|||
for {set j 0} {$j < $n} {incr j} { |
|||
puts -nonewline \t[::math::choose [expr {$i+$j}] $i] |
|||
} |
|||
puts "" |
|||
} |
|||
} |
|||
} |
|||
foreach type {upper lower symmetric} { |
|||
puts "\n* $type" |
|||
pascal::$type 5 |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre> |
|||
* upper |
|||
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 |
|||
* lower |
|||
1 0 0 0 0 |
|||
1 1 0 0 0 |
|||
1 2 1 0 0 |
|||
1 3 3 1 0 |
|||
1 4 6 4 1 |
|||
* symmetric |
|||
1 1 1 1 1 |
|||
1 2 3 4 5 |
|||
1 3 6 10 15 |
|||
1 4 10 20 35 |
|||
1 5 15 35 70 |
|||
</pre> |
</pre> |
||
Revision as of 03:02, 4 May 2015
You are encouraged to solve this task according to the task description, using any language you may know.
A pascal matrix is a two-dimensional square matrix holding numbers from Pascal's triangle, also known as binomial coefficients and which can be shown as nCr.
Showing truncated 5-by-5 matrices M[i, j] for i,j in range 0..4.
A Pascal upper-triangular matrix is populated with jCi
[[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]]
A Pascal lower-triangular matrix is populated with iCj (the transpose of the upper-triangular matrix).
[[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 2, 1, 0, 0], [1, 3, 3, 1, 0], [1, 4, 6, 4, 1]]
A Pascal symmetric matrix is populated with i+jCi
[[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 6, 10, 15], [1, 4, 10, 20, 35], [1, 5, 15, 35, 70]]
The task is to write functions capable of generating each of the three forms of n-by-n matrices.
Use those functions to display upper, lower, and symmetric Pascal 5-by-5 matrices on this page. The output should distinguish between different matrices and the rows of each matrix (No showing a list of 25 numbers assuming the reader should split it into rows).
- Note
- The Cholesky decomposition of a Pascal symmetric matrix is the Pascal lower-triangle matrix of the same size.
Common Lisp
<lang lisp>(defun pascal-lower (n &aux (a (make-array (list n n) :initial-element 0)))
(dotimes (i n)
(setf (aref a i 0) 1))
(dotimes (i (1- n) a)
(dotimes (j (1- n))
(setf (aref a (1+ i) (1+ j))
(+ (aref a i j)
(aref a i (1+ j)))))))
(defun pascal-upper (n &aux (a (make-array (list n n) :initial-element 0)))
(dotimes (i n)
(setf (aref a 0 i) 1))
(dotimes (i (1- n) a)
(dotimes (j (1- n))
(setf (aref a (1+ j) (1+ i))
(+ (aref a j i)
(aref a (1+ j) i))))))
(defun pascal-symmetric (n &aux (a (make-array (list n n) :initial-element 0)))
(dotimes (i n)
(setf (aref a i 0) 1 (aref a 0 i) 1))
(dotimes (i (1- n) a)
(dotimes (j (1- n))
(setf (aref a (1+ i) (1+ j))
(+ (aref a (1+ i) j)
(aref a i (1+ j)))))))
? (pascal-lower 4)
- 2A((1 0 0 0) (1 1 0 0) (1 2 1 0) (1 3 3 1))
? (pascal-upper 4)
- 2A((1 1 1 1) (0 1 2 3) (0 0 1 3) (0 0 0 1))
? (pascal-symmetric 4)
- 2A((1 1 1 1) (1 2 3 4) (1 3 6 10) (1 4 10 20))
- In case one really insists in printing the array row by row
(defun print-matrix (a)
(let ((p (array-dimension a 0))
(q (array-dimension a 1)))
(dotimes (i p)
(dotimes (j q)
(princ (aref a i j))
(princ #\Space))
(terpri))))
? (print-matrix (pascal-lower 4)) 1 0 0 0 1 1 0 0 1 2 1 0 1 3 3 1</lang>
Fortran
The following program uses features of Fortran 2003.
<lang fortran>module pascal
implicit none
contains
function pascal_lower(n) result(a)
integer :: n, i, j
integer, allocatable :: a(:, :)
allocate(a(n, n))
a = 0
do i = 1, n
a(i, 1) = 1
end do
do i = 2, n
do j = 2, i
a(i, j) = a(i - 1, j) + a(i - 1, j - 1)
end do
end do
end function
function pascal_upper(n) result(a)
integer :: n, i, j
integer, allocatable :: a(:, :)
allocate(a(n, n))
a = 0
do i = 1, n
a(1, i) = 1
end do
do i = 2, n
do j = 2, i
a(j, i) = a(j, i - 1) + a(j - 1, i - 1)
end do
end do
end function
function pascal_symmetric(n) result(a)
integer :: n, i, j
integer, allocatable :: a(:, :)
allocate(a(n, n))
a = 0
do i = 1, n
a(i, 1) = 1
a(1, i) = 1
end do
do i = 2, n
do j = 2, n
a(i, j) = a(i - 1, j) + a(i, j - 1)
end do
end do
end function
subroutine print_matrix(a)
integer :: a(:, :)
integer :: n, i
n = ubound(a, 1)
do i = 1, n
print *, a(i, :)
end do
end subroutine
end module
program ex_pascal
use pascal implicit none integer :: n integer, allocatable :: a(:, :) print *, "Size?" read *, n print *, "Lower Pascal Matrix" a = pascal_lower(n) call print_matrix(a) print *, "Upper Pascal Matrix" a = pascal_upper(n) call print_matrix(a) print *, "Symmetric Pascal Matrix" a = pascal_symmetric(n) call print_matrix(a)
end program</lang>
<lang> Size? 5
Lower Pascal Matrix
1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
Upper Pascal Matrix
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
Symmetric Pascal Matrix
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70</lang>
J
<lang J> !/~ 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
!~/~ i. 5
1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1
(["0/!+/)~ i. 5
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70</lang>
Explanation:
x!y is the number of ways of picking x balls (unordered) from a bag of y balls and x!/y for list x and list y gives a table where rows correspond to the elements of x and the columns correspond to the elements of y. Meanwhile !/~y is equivalent to y!/y (and i.y just counts the first y non-negative integers).
Also, x!~y is y!x (and the second example otherwise follows the same pattern as the first example.
For the final example we use an unadorned ! but prepare tables for its x and y values. Its right argument is a sum table, and its left argument is a left identity table. They look like this:
<lang J> (+/)~ i. 5 0 1 2 3 4 1 2 3 4 5 2 3 4 5 6 3 4 5 6 7 4 5 6 7 8
(["0/)~ i. 5
0 0 0 0 0 1 1 1 1 1 2 2 2 2 2 3 3 3 3 3 4 4 4 4 4</lang>
The parenthesis in these last two examples are redundant - they could have been omitted without changing the result, but were left in place for emphasis.
jq
<lang jq># Generic functions
- Note: 'transpose' is defined in recent versions of jq
def transpose:
if (.[0] | length) == 0 then [] else [map(.[0])] + (map(.[1:]) | transpose) end ;
- Create an m x n matrix with init as the initial value
def matrix(m; n; init):
if m == 0 then []
elif m == 1 then [range(0;n) | init]
elif m > 0 then
matrix(1;n;init) as $row
| [range(0;m) | $row ]
else error("matrix\(m);_;_) invalid")
end ;
- A simple pretty-printer for a 2-d matrix
def pp:
def pad(n): tostring | (n - length) * " " + .;
def row: reduce .[] as $x (""; . + ($x|pad(4)));
reduce .[] as $row (""; . + "\n\($row|row)");</lang>
<lang jq># n is input def pascal_upper:
. as $n
| matrix($n; $n; 0)
| .[0] = [range(0; $n) | 1 ]
| reduce range(1; $n) as $i
(.; reduce range($i; $n) as $j
(.; .[$i][$j] = .[$i-1][$j-1] + .[$i][$j-1]) ) ;
def pascal_lower:
pascal_upper | transpose ;
- n is input
def pascal_symmetric:
. as $n
| matrix($n; $n; 1)
| reduce range(1; $n) as $i
(.; reduce range(1; $n) as $j
(.; .[$i][$j] = .[$i-1][$j] + .[$i][$j-1]) ) ;</lang>
Example: <lang jq>5 | ("\nUpper:", (pascal_upper | pp),
"\nLower:", (pascal_lower | pp), "\nSymmetric:", (pascal_symmetric | pp) )</lang>
- Output:
<lang sh>$ jq -r -n -f Pascal_matrix_generation.jq
Upper:
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
Lower:
1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1
Symmetric:
1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70</lang>
Perl 6
Here is a rather more general solution than required. The grow-matrix function will grow any N by N matrix into an N+1 x N+1 matrix, using any function of the three leftward/upward neighbors, here labelled "West", "North", and "Northwest". We then define three iterator functions that can grow Pascal matrices, and use those iterators to define three constants, each of which is an infinite sequence of ever-larger Pascal matrices. Normal subscripting then pulls out the ones of the specified size. <lang perl6># Extend a matrix in 2 dimensions based on 3 neighbors. sub grow-matrix(@matrix, &func) {
my @m = @matrix.deepmap: { .clone }
my $s = +@m; # West North NorthWest
@m[$s][0] = func( 0, @m[$s-1][0], 0 );
@m[0][$s] = func( @m[0][$s-1], 0, 0 );
@m[$_][$s] = func( @m[$_][$s-1], @m[$_-1][$s], @m[$_-1][$s-1]) for 1 ..^ $s;
@m[$s][$_] = func( @m[$s][$_-1], @m[$s-1][$_], @m[$s-1][$_-1]) for 1 .. $s;
[@m];
}
- I am but mad north-northwest...
sub madd-n-nw($m) { grow-matrix $m, -> $w, $n, $nw { $n + $nw } } sub madd-w-nw($m) { grow-matrix $m, -> $w, $n, $nw { $w + $nw } } sub madd-w-n ($m) { grow-matrix $m, -> $w, $n, $nw { $w + $n } }
- Define 3 infinite sequences of Pascal matrices.
constant upper-tri := 1, &madd-w-nw ... *; constant lower-tri := 1, &madd-n-nw ... *; constant symmetric := 1, &madd-w-n ... *;
- Pull out the 4th element of each sequence.
.say for upper-tri[4][]; say ; .say for lower-tri[4][]; say ; .say for symmetric[4][];</lang>
- Output:
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 1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70
Python
Python: Summing adjacent values
<lang python>from pprint import pprint as pp
def pascal_upp(n):
s = [[0] * n for _ in range(n)]
s[0] = [1] * n
for i in range(1, n):
for j in range(i, n):
s[i][j] = s[i-1][j-1] + s[i][j-1]
return s
def pascal_low(n):
# transpose of pascal_upp(n) return [list(x) for x in zip(*pascal_upp(n))]
def pascal_sym(n):
s = [[1] * n for _ in range(n)]
for i in range(1, n):
for j in range(1, n):
s[i][j] = s[i-1][j] + s[i][j-1]
return s
if __name__ == "__main__":
n = 5
print("\nUpper:")
pp(pascal_upp(n))
print("\nLower:")
pp(pascal_low(n))
print("\nSymmetric:")
pp(pascal_sym(n))</lang>
- Output:
Upper: [[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]] Lower: [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 2, 1, 0, 0], [1, 3, 3, 1, 0], [1, 4, 6, 4, 1]] Symmetric: [[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 6, 10, 15], [1, 4, 10, 20, 35], [1, 5, 15, 35, 70]]
Python: Using a binomial coefficient generator function
<lang python>def binomialCoeff(n, k):
result = 1
for i in range(1, k+1):
result = result * (n-i+1) // i
return result
def pascal_upp(n):
return [[binomialCoeff(j, i) for j in range(n)] for i in range(n)]
def pascal_low(n):
return [[binomialCoeff(i, j) for j in range(n)] for i in range(n)]
def pascal_sym(n):
return [[binomialCoeff(i+j, i) for j in range(n)] for i in range(n)]</lang>
- Output:
(As above)
Racket
<lang racket>#lang racket (require math/number-theory)
(define (pascal-upper-matrix n)
(for/list ((i n)) (for/list ((j n)) (j . binomial . i))))
(define (pascal-lower-matrix n)
(for/list ((i n)) (for/list ((j n)) (i . binomial . j))))
(define (pascal-symmetric-matrix n)
(for/list ((i n)) (for/list ((j n)) ((+ i j) . binomial . j))))
(define (matrix->string m)
(define col-width
(for*/fold ((rv 1)) ((r m) (c r))
(if (zero? c) rv (max rv (+ 1 (order-of-magnitude c))))))
(string-append
(string-join
(for/list ((r m))
(string-join (map (λ (c) (~a #:width col-width #:align 'right c)) r) " ")) "\n")
"\n"))
(printf "Upper:~%~a~%" (matrix->string (pascal-upper-matrix 5))) (printf "Lower:~%~a~%" (matrix->string (pascal-lower-matrix 5))) (printf "Symmetric:~%~a~%" (matrix->string (pascal-symmetric-matrix 5)))</lang>
- Output:
Upper: 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 Lower: 1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1 Symmetric: 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70
Ruby
<lang ruby>
- Symetric, upper, and lower Pascal Matrix - Nigel Galloway: May 3rd., 21015
ng = (G = 0..4).collect{[]} G.each{|n| G.each{|g| ng[n][g] = (n==0 or g==0) ? 1 : ng[n-1][g]+ng[n][g-1] }; p ng[n]}; puts nil G.each{|n| G.each{|g| ng[n][g] = g==0 ? 1 : n<g ? 0 : ng[n-1][g-1]+ng[n-1][g]}; p ng[n]}; puts nil G.each{|n| G.each{|g| ng[n][g] = n==0 ? 1 : g<n ? 0 : ng[n-1][g-1]+ng[n][g-1]}; p ng[n]} </lang>
- Output:
[1, 1, 1, 1, 1] [1, 2, 3, 4, 5] [1, 3, 6, 10, 15] [1, 4, 10, 20, 35] [1, 5, 15, 35, 70] [1, 0, 0, 0, 0] [1, 1, 0, 0, 0] [1, 2, 1, 0, 0] [1, 3, 3, 1, 0] [1, 4, 6, 4, 1] [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]
Binomial coefficient:
<lang ruby>require 'pp'
def binomial_coeff(n,k) (1..k).inject(1){|res,i| res * (n-i+1) / i} end
def pascal_upper(n) (0...n).map{|i| (0...n).map{|j| binomial_coeff(j,i)}} end def pascal_lower(n) (0...n).map{|i| (0...n).map{|j| binomial_coeff(i,j)}} end def pascal_symmetric(n) (0...n).map{|i| (0...n).map{|j| binomial_coeff(i+j,j)}} end
puts "Pascal upper-triangular matrix:" pp pascal_upper(5)
puts "\nPascal lower-triangular matrix:" pp pascal_lower(5)
puts "\nPascal symmetric matrix:" pp pascal_symmetric(5)</lang>
- Output:
Pascal upper-triangular matrix: [[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]] Pascal lower-triangular matrix: [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [1, 2, 1, 0, 0], [1, 3, 3, 1, 0], [1, 4, 6, 4, 1]] Pascal symmetric matrix: [[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 6, 10, 15], [1, 4, 10, 20, 35], [1, 5, 15, 35, 70]]
Tcl
<lang Tcl> package require math
namespace eval pascal {
proc upper {n} {
for {set i 0} {$i < $n} {incr i} {
for {set j 0} {$j < $n} {incr j} {
puts -nonewline \t[::math::choose $j $i]
}
puts ""
}
}
proc lower {n} {
for {set i 0} {$i < $n} {incr i} {
for {set j 0} {$j < $n} {incr j} {
puts -nonewline \t[::math::choose $i $j]
}
puts ""
}
}
proc symmetric {n} {
for {set i 0} {$i < $n} {incr i} {
for {set j 0} {$j < $n} {incr j} {
puts -nonewline \t[::math::choose [expr {$i+$j}] $i]
}
puts ""
}
}
}
foreach type {upper lower symmetric} {
puts "\n* $type" pascal::$type 5
} </lang>
- Output:
* upper
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
* lower
1 0 0 0 0
1 1 0 0 0
1 2 1 0 0
1 3 3 1 0
1 4 6 4 1
* symmetric
1 1 1 1 1
1 2 3 4 5
1 3 6 10 15
1 4 10 20 35
1 5 15 35 70
zkl
<lang zkl>fcn binomial(n,k){ (1).reduce(k,fcn(p,i,n){ p*(n-i+1)/i },1,n) } fcn pascal_upp(n){ [[(i,j); n; n; '{ binomial(j,i) }]]:toMatrix(_) } fcn pascal_low(n){ (i,j); n; n; binomial:toMatrix(_) } fcn pascal_sym(n){ [[(i,j); n; n; '{ binomial(i+j,i) }]]:toMatrix(_) } fcn toMatrix(ns){ // turn a string of numbers into a square matrix (list of lists)
cols:=ns.len().toFloat().sqrt().toInt(); ns.pump(List,T(Void.Read,cols-1),List.create)
}</lang> <lang zkl>fcn prettyPrint(m){ // m is a list of lists
fmt:=("%3d "*m.len() + "\n").fmt;
m.pump(String,'wrap(col){ fmt(col.xplode()) });
} const N=5; println("Upper:\n", pascal_upp(N):prettyPrint(_)); println("Lower:\n", pascal_low(N):prettyPrint(_)); println("Symmetric:\n",pascal_sym(N):prettyPrint(_));</lang>
- Output:
Upper: 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 Lower: 1 0 0 0 0 1 1 0 0 0 1 2 1 0 0 1 3 3 1 0 1 4 6 4 1 Symmetric: 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 1 4 10 20 35 1 5 15 35 70