Pascal matrix generation: Difference between revisions
m (added a ;Task: (bold) header, add other whitespace in the task's preamble, used a larger font for some mathematical expressions to better show the italics, super- and subscripts so they can be read easier. s) |
|||
| Line 613: | Line 613: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{incorrect|Julia|Computing max(A,A') does '''not''' produce the symmetric Pascal matrix.}} |
|||
<lang Julia>julia> n = 5; |
<lang Julia>julia> n = 5; |
||
julia> A = zeros(Int64,n,n); |
julia> A = zeros(Int64,n,n); |
||
| Line 646: | Line 647: | ||
1 4 6 4 1 |
1 4 6 4 1 |
||
</lang> |
</lang> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
{{works with|jq|1.4}} |
{{works with|jq|1.4}} |
||
Revision as of 11:57, 6 July 2016
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.
Shown below are truncated 5-by-5 matrices M[i, j] for i,j in range 0..4.
A Pascal upper-triangular matrix that 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 that 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 that 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]]
- Task
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.
C
<lang c>
- include <stdio.h>
- include <stdlib.h>
void pascal_upp(int **mat, int n) {
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (i < j)
mat[i][j] = 0;
else if (i == j || j == 0)
mat[i][j] = 1;
else
mat[i][j] = mat[i - 1][j - 1] + mat[i - 1][j];
}
void pascal_low(int **mat, int n) {
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (i > j)
mat[i][j] = 0;
else if (i == j || i == 0)
mat[i][j] = 1;
else
mat[i][j] = mat[i - 1][j - 1] + mat[i][j - 1];
}
void pascal_sym(int **mat, int n) {
int i, j;
for (i = 0; i < n; ++i)
for (j = 0; j < n; ++j)
if (i == 0 || j == 0)
mat[i][j] = 1;
else
mat[i][j] = mat[i - 1][j] + mat[i][j - 1];
}
int main(int argc, char * argv[]) {
int **mat; int i, j, n;
/* Input size of the matrix */ n = 5;
/* Matrix allocation */
mat = calloc(n, sizeof(int *));
for (i = 0; i < n; ++i)
mat[i] = calloc(n, sizeof(int));
/* Matrix computation */
printf("=== Pascal upper matrix ===\n");
pascal_upp(mat, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
printf("%4d%c", mat[i][j], j < n - 1 ? ' ' : '\n');
printf("=== Pascal lower matrix ===\n");
pascal_low(mat, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
printf("%4d%c", mat[i][j], j < n - 1 ? ' ' : '\n');
printf("=== Pascal lower matrix ===\n");
pascal_sym(mat, n);
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
printf("%4d%c", mat[i][j], j < n - 1 ? ' ' : '\n');
return 0;
} </lang>
- Output:
=== Pascal upper 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 lower 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 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
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 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
? (print-matrix (pascal-upper 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
? (print-matrix (pascal-symmetric 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>
D
<lang d>import std.stdio, std.bigint, std.range, std.algorithm;
auto binomialCoeff(in uint n, in uint k) pure nothrow {
BigInt result = 1;
foreach (immutable i; 1 .. k + 1)
result = result * (n - i + 1) / i;
return result;
}
auto pascalUpp(in uint n) pure nothrow {
return n.iota.map!(i => n.iota.map!(j => binomialCoeff(j, i)));
}
auto pascalLow(in uint n) pure nothrow {
return n.iota.map!(i => n.iota.map!(j => binomialCoeff(i, j)));
}
auto pascalSym(in uint n) pure nothrow {
return n.iota.map!(i => n.iota.map!(j => binomialCoeff(i + j, i)));
}
void main() {
enum n = 5;
writefln("Upper:\n%(%(%2d %)\n%)", pascalUpp(n));
writefln("\nLower:\n%(%(%2d %)\n%)", pascalLow(n));
writefln("\nSymmetric:\n%(%(%2d %)\n%)", pascalSym(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
Elixir
<lang elixir>defmodule Pascal do
def upper_triangle(n) do
Enum.reduce((for i<-1..n, j<-1..n, do: {i,j}), Map.new, fn {i,j},acc ->
val = cond do
i==1 -> 1
j 0
true -> Dict.get(acc, {i-1, j-1}) + Dict.get(acc, {i, j-1})
end
Dict.put(acc, {i,j}, val)
end) |> print(1..n)
end
def lower_triangle(n) do
Enum.reduce((for i<-1..n, j<-1..n, do: {i,j}), Map.new, fn {i,j},acc ->
val = cond do
j==1 -> 1
i<j -> 0
true -> Dict.get(acc, {i-1, j-1}) + Dict.get(acc, {i-1, j})
end
Dict.put(acc, {i,j}, val)
end) |> print(1..n)
end
def symmetic_triangle(n) do
Enum.reduce((for i<-1..n, j<-1..n, do: {i,j}), Map.new, fn {i,j},acc ->
val = if i==1 or j==1, do: 1,
else: Dict.get(acc, {i-1, j}) + Dict.get(acc, {i, j-1})
Dict.put(acc, {i,j}, val)
end) |> print(1..n)
end
def print(matrix, range) do
Enum.each(range, fn i ->
Enum.map(range, fn j -> Dict.get(matrix, {i,j}) end) |> IO.inspect
end)
end
end
IO.puts "Pascal upper-triangular matrix:" Pascal.upper_triangle(5) IO.puts "Pascal lower-triangular matrix:" Pascal.lower_triangle(5) IO.puts "Pascal symmetric matrix:" Pascal.symmetic_triangle(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]
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>
Haskell
<lang haskell>import Data.List (transpose) import System.Environment (getArgs) import Text.Printf (printf)
-- Pascal's triangle. pascal :: Int pascal = iterate (\row -> 1 : zipWith (+) row (tail row) ++ [1]) [1]
-- The n by n Pascal lower triangular matrix. pascLow :: Int -> Int pascLow n = zipWith (\row i -> row ++ replicate (n-i) 0) (take n pascal) [1..]
-- The n by n Pascal upper triangular matrix. pascUp :: Int -> Int pascUp = transpose . pascLow
-- The n by n Pascal symmetric matrix. pascSym :: Int -> Int pascSym n = take n . map (take n) . transpose $ pascal
-- Format and print a matrix. printMat :: String -> Int -> IO () printMat title mat = do
putStrLn $ title ++ "\n" mapM_ (putStrLn . concatMap (printf " %2d")) mat putStrLn "\n"
main :: IO () main = do
ns <- fmap (map read) getArgs
case ns of
[n] -> do printMat "Lower triangular" $ pascLow n
printMat "Upper triangular" $ pascUp n
printMat "Symmetric" $ pascSym n
_ -> error "Usage: pascmat <number>"</lang>
- Output:
Lower triangular 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 triangular 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 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
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.
Java
<lang java>import static java.lang.System.out; import java.util.List; import java.util.function.Function; import java.util.stream.*; import static java.util.stream.Collectors.toList; import static java.util.stream.IntStream.range;
public class PascalMatrix {
static int binomialCoef(int n, int k) {
int result = 1;
for (int i = 1; i <= k; i++)
result = result * (n - i + 1) / i;
return result;
}
static List<IntStream> pascal(int n, Function<Integer, IntStream> f) {
return range(0, n).mapToObj(i -> f.apply(i)).collect(toList());
}
static List<IntStream> pascalUpp(int n) {
return pascal(n, i -> range(0, n).map(j -> binomialCoef(j, i)));
}
static List<IntStream> pascalLow(int n) {
return pascal(n, i -> range(0, n).map(j -> binomialCoef(i, j)));
}
static List<IntStream> pascalSym(int n) {
return pascal(n, i -> range(0, n).map(j -> binomialCoef(i + j, i)));
}
static void print(String label, List<IntStream> result) {
out.println("\n" + label);
for (IntStream row : result) {
row.forEach(i -> out.printf("%2d ", i));
System.out.println();
}
}
public static void main(String[] a) {
print("Upper: ", pascalUpp(5));
print("Lower: ", pascalLow(5));
print("Symmetric:", pascalSym(5));
}
}</lang>
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
Julia
<lang Julia>julia> n = 5; julia> A = zeros(Int64,n,n); julia> A[1,:] = ones(Int64,n); julia> for i = 2:n
v = A[i-1,i-1:n];
w = cumsum(v,2);
A[i,i:n] = w[1:end-1];
end
julia> A 5x5 Array{Int64,2}:
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
julia> A' 5x5 Array{Int64,2}:
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
julia> max(A,A') 5x5 Array{Int64,2}:
1 1 1 1 1 1 1 2 3 4 1 2 1 3 6 1 3 3 1 4 1 4 6 4 1
</lang>
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>
Lua
<lang Lua>function factorial (n)
local f = 1
for i = 2, n do
f = f * i
end
return f
end
function binomial (n, k)
if k > n then return 0 end return factorial(n) / (factorial(k) * factorial(n - k))
end
function pascalMatrix (form, size)
local matrix = {}
for row = 1, size do
matrix[row] = {}
for col = 1, size do
if form == "upper" then
matrix[row][col] = binomial(col - 1, row - 1)
end
if form == "lower" then
matrix[row][col] = binomial(row - 1, col - 1)
end
if form == "symmetric" then
matrix[row][col] = binomial(row + col - 2, col - 1)
end
end
end
matrix.form = form:sub(1, 1):upper() .. form:sub(2, -1)
return matrix
end
function show (mat)
print(mat.form .. ":")
for i = 1, #mat do
for j = 1, #mat[i] do
io.write(mat[i][j] .. "\t")
end
print()
end
print()
end
for _, form in pairs({"upper", "lower", "symmetric"}) do
show(pascalMatrix(form, 5))
end</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
Mathematica
One solution is to generate a symmetric Pascal matrix then use the built in method to compute the upper Pascal matrix. This would be done as follows: <lang Mathematica>symPascal[size_] := NestList[Accumulate, Table[1, {k, size}], size - 1]
upperPascal[size_] := CholeskyDecomposition[symPascal@size]
lowerPascal[size_] := Transpose@CholeskyDecomposition[symPascal@size]
Column[MapThread[
Labeled[Grid[#1@5], #2, Top] &, {{upperPascal, lowerPascal,
symPascal}, {"Upper", "Lower", "Symmetric"}}]]</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
It is also possible to directly compute a lower Pascal matrix as follows: <lang Mathematica>lowerPascal[size_] :=
MatrixExp[
SparseArray[{Band[{2, 1}] -> Range[size - 1]}, {size, size}]]]</lang>
But since the builtin function MatrixExp works by first computing eigenvalues this is likely to be slower for large Pascal matrices
Perl
<lang Perl>#!/usr/bin/perl use warnings; use strict; use feature qw{ say };
sub upper {
my ($i, $j) = @_;
my @m;
for my $x (0 .. $i - 1) {
for my $y (0 .. $j - 1) {
$m[$x][$y] = $x > $y ? 0
: ! $x || $x == $y ? 1
: $m[$x-1][$y-1] + $m[$x][$y-1];
}
}
return \@m
}
sub lower {
my ($i, $j) = @_;
my @m;
for my $x (0 .. $i - 1) {
for my $y (0 .. $j - 1) {
$m[$x][$y] = $x < $y ? 0
: ! $x || $x == $y ? 1
: $m[$x-1][$y-1] + $m[$x-1][$y];
}
}
return \@m
}
sub symmetric {
my ($i, $j) = @_;
my @m;
for my $x (0 .. $i - 1) {
for my $y (0 .. $j - 1) {
$m[$x][$y] = ! $x || ! $y ? 1
: $m[$x-1][$y] + $m[$x][$y-1];
}
}
return \@m
}
sub pretty {
my $m = shift;
for my $row (@$m) {
say join ', ', @$row;
}
}
pretty(upper(5, 5));
say '-' x 14;
pretty(lower(5, 5));
say '-' x 14;
pretty(symmetric(5, 5));</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
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
PL/I
<lang pli>*process source attributes xref or(!);
pat: Proc Options(main); Dcl (HBOUND,MAX,RIGHT) Builtin; Dcl SYSPRINT Print; Dcl N Bin Fixed(31) Init(5); Dcl pd Char(500) Var; Dcl fact(0:10) Bin Fixed(31); Dcl pt(0:500) Bin Fixed(31); Call mk_fact(fact);
Call Pascal(n,'U',pt); Call show('Pascal upper triangular matrix');
Call Pascal(n,'L',pt); Call show('Pascal lower triangular matrix');
Call Pascal(n,'S',pt); Call show('Pascal symmetric matrix' );
Pascal: proc(n,which,dd);
Dcl n Bin Fixed(31);
Dcl which Char(1);
Dcl (i,j,k) Bin Fixed(31);
Dcl dd(0:500) Bin Fixed(31);
k=0;
dd(0)=0;
do i=0 To n-1;
Do j=0 To n-1;
k+=1;
Select(which);
When('U') dd(k)=comb((j), (i));
When('L') dd(k)=comb((i), (j));
When('S') dd(k)=comb((i+j),(i));
Otherwise;
End;
dd(0)=max(dd(0),dd(k));
End;
End;
End;
mk_fact: Proc(f); Dcl f(0:*) Bin Fixed(31); Dcl i Bin Fixed(31); f(0)=1; Do i=1 To hbound(f); f(i)=f(i-1)*i; End; End;
comb: proc(x,y) Returns(pic'z9');
Dcl (x,y) Bin Fixed(31);
Dcl (j,z) Bin Fixed(31);
Dcl res Pic'Z9';
Select;
When(x=y) res=1;
When(y>x) res=0;
Otherwise Do;
If x-y<y then
y=x-y;
z=1;
do j=x-y+1 to x;
z=z*j;
End;
res=z/fact(y);
End;
End;
Return(res);
End;
show: Proc(head);
Dcl head Char(*);
Dcl (n,r,c,pl) Bin Fixed(31) Init(0);
Dcl row Char(50) Var;
Dcl p Pic'z9';
If pt(0)<10 Then pl=1;
Else pl=2;
Dcl sep(5) Char(1) Init((4)(1)',',']');
Put Edit(' ',head)(Skip,a);
do r=1 To 5;
if r=1 then row='[[';
else row=' [';
do c=1 To 5;
n+=1;
p=pt(n);
row=row!!right(p,pl)!!sep(c);
End;
Put Edit(row)(Skip,a);
End;
Put Edit(']')(A);
End;
End;</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]]
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)
R
<lang r>lower.pascal <- function(n) {
a <- matrix(0, n, n)
a[, 1] <- 1
if (n > 1) {
for (i in 2:n) {
j <- 2:i
a[i, j] <- a[i - 1, j - 1] + a[i - 1, j]
}
}
a
}
- Alternate version
lower.pascal.alt <- function(n) {
a <- matrix(0, n, n)
a[, 1] <- 1
if (n > 1) {
for (j in 2:n) {
i <- j:n
a[i, j] <- cumsum(a[i - 1, j - 1])
}
}
a
}
- While it's possible to modify lower.pascal to get the upper matrix,
- here we simply transpose the lower one.
upper.pascal <- function(n) t(lower.pascal(n))
symm.pascal <- function(n) {
a <- matrix(0, n, n)
a[, 1] <- 1
for (i in 2:n) {
a[, i] <- cumsum(a[, i - 1])
}
a
}</lang>
The results follow
<lang r>> lower.pascal(5)
[,1] [,2] [,3] [,4] [,5]
[1,] 1 0 0 0 0 [2,] 1 1 0 0 0 [3,] 1 2 1 0 0 [4,] 1 3 3 1 0 [5,] 1 4 6 4 1 > lower.pascal.alt(5)
[,1] [,2] [,3] [,4] [,5]
[1,] 1 0 0 0 0 [2,] 1 1 0 0 0 [3,] 1 2 1 0 0 [4,] 1 3 3 1 0 [5,] 1 4 6 4 1 > upper.pascal(5)
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 1 1 [2,] 0 1 2 3 4 [3,] 0 0 1 3 6 [4,] 0 0 0 1 4 [5,] 0 0 0 0 1 > symm.pascal(5)
[,1] [,2] [,3] [,4] [,5]
[1,] 1 1 1 1 1 [2,] 1 2 3 4 5 [3,] 1 3 6 10 15 [4,] 1 4 10 20 35 [5,] 1 5 15 35 70</lang>
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
REXX
separate generation
Commentary: 1/3 of the REXX program deals with the displaying of the matrix. <lang rexx>/*REXX program generates and displays three forms of an NxN Pascal matrix. */ numeric digits 50 /*be able to calculate huge factorials.*/ parse arg N . /*obtain the optional matrix size (N).*/ if N== then N=5 /*Not specified? Then use the default.*/
call show N, upp(N), 'Pascal upper triangular matrix'
call show N, low(N), 'Pascal lower triangular matrix'
call show N, sym(N), 'Pascal symmetric matrix'
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ upp: procedure; parse arg N; $= /*gen Pascal upper triangular matrix. */
do i=0 for N; do j=0 for N; $=$ comb(j, i); end; end; return $
/*──────────────────────────────────────────────────────────────────────────────────────*/ low: procedure; parse arg N; $= /*gen Pascal lower triangular matrix. */
do i=0 for N; do j=0 for N; $=$ comb(i, j); end; end; return $
/*──────────────────────────────────────────────────────────────────────────────────────*/ sym: procedure; parse arg N; $= /*generate Pascal symmetric matrix. */
do i=0 for N; do j=0 for N; $=$ comb(i+j, i); end; end; return $
/*──────────────────────────────────────────────────────────────────────────────────────*/ !: procedure; parse arg x; !=1; do j=2 to x; !=!*j; end; return ! /*──────────────────────────────────────────────────────────────────────────────────────*/ comb: procedure; parse arg x,y; if x=y then return 1 /* {=} case.*/
if y>x then return 0 /* {>} case.*/
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _ / !(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: procedure; parse arg s,@; w=0; #=0 /*get args. */
do x=1 for s**2; w=max(w,1+length(word(@,x))); end
say; say center(arg(3), 50, '─') /*show title*/
do r=1 for s; if r==1 then $='[[' /*row 1 */
else $=' [' /*rows 2 N*/
do c=1 for s; #=#+1; e= (c==s) /*e ≡ "end".*/
$=$ || right(word(@, #), w) || left(',', \e) || left("]", e)
end /*c*/ /* [↑] row.*/
say $ || left(',', r\==s)left("]", r==s) /*show row. */
end /*r*/
return</lang>
output using the default input:
──────────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]]
consolidated generation
This REXX version uses a consolidated generation subroutine, even though this Rosetta Code implies to use functions (instead of a single function). <lang rexx>/*REXX program generates and displays three forms of an NxN Pascal matrix. */ numeric digits 50 /*be able to calculate huge factorials.*/ parse arg N . /*obtain the optional matrix size (N).*/ if N== then N=5 /*Not specified? Then use the default.*/
call show N, Pmat(N, 'upper'), 'Pascal upper triangular matrix'
call show N, Pmat(N, 'lower'), 'Pascal lower triangular matrix'
call show N, Pmat(N, 'sym') , 'Pascal symmetric matrix'
exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ Pmat: procedure; parse arg N; $= /*generate a format of a Pascal matrix.*/
arg , ? /*get uppercase version of the 2nd arg.*/
do i=0 for N; do j=0 for N /* [↓] pick a format to use. */
if abbrev('UPPER' ,?,1) then $=$ comb(j , i)
if abbrev('LOWER' ,?,1) then $=$ comb(i , j)
if abbrev('SYMMETRICAL',?,1) then $=$ comb(i+j, j)
end /*j*/ /* ↑ */
end /*i*/ /* │ */
return $ /* └───min. abbreviation is 1 char.*/
/*──────────────────────────────────────────────────────────────────────────────────────*/ !: procedure; parse arg x; !=1; do j=2 to x; !=!*j; end; return ! /*──────────────────────────────────────────────────────────────────────────────────────*/ comb: procedure; parse arg x,y; if x=y then return 1 /* {=} case.*/
if y>x then return 0 /* {>} case.*/
if x-y<y then y=x-y; _=1; do j=x-y+1 to x; _=_*j; end; return _ / !(y)
/*──────────────────────────────────────────────────────────────────────────────────────*/ show: procedure; parse arg s,@; w=0; #=0 /*get args. */
do x=1 for s**2; w=max(w,1+length(word(@,x))); end
say; say center(arg(3), 50, '─') /*show title*/
do r=1 for s; if r==1 then $='[[' /*row 1 */
else $=' [' /*rows 2 N*/
do c=1 for s; #=#+1; e= (c==s) /*e ≡ "end".*/
$=$ || right(word(@, #), w) || left(', ',\e) || left("]", e)
end /*c*/ /* [↑] row.*/
say $ || left(',', r\==s)left(']', r==s) /*show row. */
end /*r*/
return</lang>
output is identical to the 1st REXX version.
Ruby
Summing adjacent values: <lang ruby>#Upper, lower, and symetric Pascal Matrix - Nigel Galloway: May 3rd., 21015 require 'pp'
ng = (g = 0..4).collect{[]} g.each{|i| g.each{|j| ng[i][j] = i==0 ? 1 : j<i ? 0 : ng[i-1][j-1]+ng[i][j-1]}} pp ng; puts g.each{|i| g.each{|j| ng[i][j] = j==0 ? 1 : i<j ? 0 : ng[i-1][j-1]+ng[i-1][j]}} pp ng; puts g.each{|i| g.each{|j| ng[i][j] = (i==0 or j==0) ? 1 : ng[i-1][j ]+ng[i][j-1]}} pp ng</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]]
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]]
Sidef
<lang ruby>func grow_matrix(matrix, callback) {
var m = matrix; var s = m.len; m[s][0] = callback(0, m[s-1][0], 0); m[0][s] = callback(m[0][s-1], 0, 0);
- 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
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
VBScript
<lang vb> Function pascal_upper(i,j) WScript.StdOut.Write "Pascal Upper" WScript.StdOut.WriteLine For l = i To j For m = i To j If l <= m Then WScript.StdOut.Write binomial(m,l) & vbTab Else WScript.StdOut.Write 0 & vbTab End If Next WScript.StdOut.WriteLine Next WScript.StdOut.WriteLine End Function
Function pascal_lower(i,j) WScript.StdOut.Write "Pascal Lower" WScript.StdOut.WriteLine For l = i To j For m = i To j If l >= m Then WScript.StdOut.Write binomial(l,m) & vbTab Else WScript.StdOut.Write 0 & vbTab End If Next WScript.StdOut.WriteLine Next WScript.StdOut.WriteLine End Function
Function pascal_symmetric(i,j) WScript.StdOut.Write "Pascal Symmetric" WScript.StdOut.WriteLine For l = i To j For m = i To j WScript.StdOut.Write binomial(l+m,m) & vbTab Next WScript.StdOut.WriteLine Next End Function
Function binomial(n,k) binomial = factorial(n)/(factorial(n-k)*factorial(k)) End Function
Function factorial(n) If n = 0 Then factorial = 1 Else For i = n To 1 Step -1 If i = n Then factorial = n Else factorial = factorial * i End If Next End If End Function
'Test driving Call pascal_upper(0,4) Call pascal_lower(0,4) Call pascal_symmetric(0,4) </lang>
- Output:
Pascal 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 Pascal 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 Pascal 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(_) } // [[..]] is list comprehension 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