Pascal's triangle
From Rosetta Code
You are encouraged to solve this task according to the task description, using any language you may know.
1 1 1 1 2 1 1 3 3 1
where each element of each row is either 1 or the sum of the two elements right above it. For example, the next row would be 1 (since the first element of each row doesn't have two elements above it), 4 (1 + 3), 6 (3 + 3), 4 (3 + 1), and 1 (since the last element of each row doesn't have two elements above it). Each row n (starting with row 0 at the top) shows the coefficients of the binomial expansion of (x + y)n.
Write a function that prints out the first n rows of the triangle (with f(1) yielding the row consisting of only the element 1). This can be done either by summing elements from the previous rows or using a binary coefficient or combination function. Behavior for n <= 0 does not need to be uniform, but should be noted.
[edit] Ada
with Ada.Integer_Text_Io; use Ada.Integer_Text_Io;
with Ada.Text_Io; use Ada.Text_Io;
procedure Pascals_Triangle is
type Row is array(Positive range <>) of Integer;
type Row_Access is access Row;
type Triangle is array(Positive range <>) of Row_Access;
function General_Triangle(Depth : Positive) return Triangle is
Result : Triangle(1..Depth);
begin
for I in Result'range loop
Result(I) := new Row(1..I);
for J in 1..I loop
if J = Result(I)'First or else J = Result(I)'Last then
Result(I)(J) := 1;
else
Result(I)(J) := Result(I - 1)(J - 1) + Result(I - 1)(J);
end if;
end loop;
end loop;
return Result;
end General_Triangle;
procedure Print(Item : Triangle) is
begin
for I in Item'range loop
for J in 1..I loop
Put(Item => Item(I)(J), Width => 3);
end loop;
New_Line;
end loop;
end Print;
begin
Print(General_Triangle(7));
end Pascals_Triangle;
[edit] ALGOL 68
PRIO MINLWB = 8, MAXUPB = 8;
OP MINLWB = ([]INT a,b)INT: (LWB a<LWB b|LWB a|LWB b),
MAXUPB = ([]INT a,b)INT: (UPB a>UPB b|UPB a|UPB b);
OP + = ([]INT a,b)[]INT:(
[a MINLWB b:a MAXUPB b]INT out; FOR i FROM LWB out TO UPB out DO out[i]:= 0 OD;
out[LWB a:UPB a] := a; FOR i FROM LWB b TO UPB b DO out[i]+:= b[i] OD;
out
);
INT width = 4, stop = 9;
FORMAT centre = $n((stop-UPB row+1)*width OVER 2)(q)$;
FLEX[1]INT row := 1; # example of rowing #
FOR i WHILE
printf((centre, $g(-width)$, row, $l$));
# WHILE # i < stop DO
row := row[AT 1] + row[AT 2]
OD
Output:
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
[edit] APL
Pascal' s triangle of order ⍵
{A←0,⍳⍵ ⋄ ⍉A∘.!A}
example
{A←0,⍳⍵ ⋄ ⍉A∘.!A} 3
1 0 0 0 1 1 0 0 1 2 1 0 1 3 3 1
[edit] AutoHotkey
ahk forum: discussion
n := 8, p0 := "1" ; 1+n rows of Pascal's triangle
Loop %n% {
p := "p" A_Index, %p% := v := 1, q := "p" A_Index-1
Loop Parse, %q%, %A_Space%
If (A_Index > 1)
%p% .= " " v+A_LoopField, v := A_LoopField
%p% .= " 1"
}
; Triangular Formatted output
VarSetCapacity(tabs,n,Asc("`t"))
t .= tabs "`t1"
Loop %n% {
t .= "`n" SubStr(tabs,A_Index)
Loop Parse, p%A_Index%, %A_Space%
t .= A_LoopField "`t`t"
}
Gui Add, Text,, %t% ; Show result in a GUI
Gui Show
Return
GuiClose:
ExitApp
[edit] AWK
$ awk 'BEGIN{for(i=0;i<6;i++){c=1;r=c;for(j=0;j<i;j++){c*=(i-j)/(j+1);r=r" "c};print r}}'
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
[edit] BASIC
[edit] Summing from Previous Rows
Works with: FreeBASIC This implementation uses an array to store one row of the triangle. DIM initializes the array values to zero. For first row, "1" is then stored in the array. To calculate values for next row, the value in cell (i-1) is added to each cell (i). This summing is done from right to left so that it can be done on-place, without using a tmp buffer. Because of symmetry, the values can be displayed from left to right.
Space for max 5 digit numbers is reserved when formatting the display. The maximum size of triangle is 100 rows, but in practice it is limited by screen space. If the user enters value less than 1, the first row is still always displayed.
DIM i AS Integer
DIM row AS Integer
DIM nrows AS Integer
DIM values(100) AS Integer
INPUT "Number of rows: "; nrows
values(1) = 1
PRINT TAB((nrows)*3);" 1"
FOR row = 2 TO nrows
PRINT TAB((nrows-row)*3+1);
FOR i = row TO 1 STEP -1
values(i) = values(i) + values(i-1)
PRINT USING "##### "; values(i);
NEXT i
NEXT row
[edit] C
Translation of: Fortran
#include <stdio.h>
void pascaltriangle(unsigned int n)
{
unsigned int c, i, j, k;
for(i=0; i < n; i++) {
c = 1;
for(j=1; j <= 2*(n-1-i); j++) printf(" ");
for(k=0; k <= i; k++) {
printf("%3d ", c);
c = c * (i-k)/(k+1);
}
printf("\n");
}
}
int main()
{
pascaltriangle(8);
return 0;
}
[edit] C++
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
void genPyrN(int rows) {
if (rows < 0) return;
// save the last row here
std::vector<int> last(1, 1);
std::cout << last[0] << std::endl;
for (int i = 1; i <= rows; i++) {
// work on the next row
std::vector<int> thisRow;
thisRow.reserve(i+1);
thisRow.push_back(last.front()); // beginning of row
std::transform(last.begin(), last.end()-1, last.begin()+1, std::back_inserter(thisRow), std::plus<int>()); // middle of row
thisRow.push_back(last.back()); // end of row
for (int j = 0; j <= i; j++)
std::cout << thisRow[j] << " ";
std::cout << std::endl;
last.swap(thisRow);
}
}
[edit] C#
Translation of: Fortran Produces no output when n is less than or equal to zero.
using System;
namespace RosettaCode {
class PascalsTriangle {
public void CreateTriangle(int n) {
if (n > 0) {
for (int i = 0; i < n; i++) {
int c = 1;
Console.Write(" ".PadLeft(2 * (n - 1 - i)));
for (int k = 0; k <= i; k++) {
Console.Write("{0}", c.ToString().PadLeft(3));
c = c * (i - k) / (k + 1);
}
Console.WriteLine();
}
}
}
}
}
[edit] Clojure
For n < 1, prints nothing, always returns nil. Copied from the Common Lisp implementation below, but with local functions and explicit tail-call-optimized recursion (recur).
(defn pascal [n]
(let [newrow (fn newrow [lst ret]
(if lst
(recur (rest lst)
(conj ret (+ (first lst) (or (second lst) 0))))
ret))
genrow (fn genrow [n lst]
(when (< 0 n)
(do (println lst)
(recur (dec n) (conj (newrow lst []) 1)))))]
(genrow n [1])))
(pascal 4)
And here's another version, using the partition function to produce the sequence of pairs in a row, which are summed and placed between two ones to produce the next row:
(defn nextrow [row]
(vec (concat [1] (map #(apply + %) (partition 2 1 row)) [1] )))
(defn pascal [n]
(assert (and (integer? n) (pos? n)))
(let [triangle (take n (iterate nextrow [1]))]
(doseq [row triangle]
(println row))))
The assert form causes the pascal function to throw an exception unless the argument is (integral and) positive.
[edit] Common Lisp
To evaluate, call (pascal n). For n < 1, it simply returns nil.
(defun pascal (n)
(genrow n '(1)))
(defun genrow (n l)
(when (< 0 n)
(print l)
(genrow (1- n) (cons 1 (newrow l)))))
(defun newrow (l)
(if (> 2 (length l))
'(1)
(cons (+ (car l) (cadr l)) (newrow (cdr l)))))
[edit] D
There is similarity between Pascal's triangle and Sierpinski triangle. Their difference are the initial line and the operation that act on the line element to produce next line. The following is a generic pascal's triangle implementation for positive number of lines output (n).
import std.stdio, std.string, std.format : fmx = format ;
string Pascal(alias dg, T, T initValue)(int n) {
string output ;
void append(T[] l) {
output ~= repeat(" ", (n - l.length + 1)*2) ;
foreach(e; l) output ~= fmx("%4s", fmx("%4s",e)) ;
output ~= "\n" ;
}
if(n > 0) {
T[][] lines = [[initValue]] ;
append(lines[0]) ;
for(int i = 1 ; i < n ; i++) {
lines ~= lines[i-1] ~ initValue ; // length + 1
for(int j = 1 ; j < lines[i-1].length ; j++)
lines[i][j] = dg(lines[i-1][j], lines[i-1][j-1]) ;
append(lines[i]) ;
}
}
return output ;
}
string delegate(int n) GenericPascal(alias dg, T, T initValue)(){
mixin Pascal!(dg, T, initValue) ;
return &Pascal ;
}
char xor(char a, char b) { return a == b ? '_' : '*' ; }
void main() {
auto pascal = GenericPascal!((int a, int b) { return a + b; }, int , 1 ) ;
auto sierpinski = GenericPascal!(xor, char, '*') ;
foreach(i ; [1,5,9]) writef(pascal(i)) ;
// an order 4 sierpinski triangle is a 2^4 lines generic pascal triangle with xor operation
foreach(i ; [16]) writef(sierpinski(i)) ;
}
[edit] E
So as not to bother with text layout, this implementation generates a HTML fragment. It uses a single mutable array, appending one 1 and adding to each value the preceding value.
def pascalsTriangle(n, out) {
def row := [].diverge(int)
out.print("<table style='text-align: center; border: 0; border-collapse: collapse;'>")
for y in 1..n {
out.print("<tr>")
row.push(1)
def skip := n - y
if (skip > 0) {
out.print(`<td colspan="$skip"></td>`)
}
for x => v in row {
out.print(`<td>$v</td><td></td>`)
}
for i in (1..!y).descending() {
row[i] += row[i - 1]
}
out.println("</tr>")
}
out.print("</table>")
}
def out := <file:triangle.html>.textWriter()
try {
pascalsTriangle(15, out)
} finally {
out.close()
}
makeCommand("yourFavoriteWebBrowser")("triangle.html")
[edit] Erlang
-import(lists).
-export([pascal/1]).
pascal(1)-> [[1]];
pascal(N) ->
L = pascal(N-1),
[H|_] = L,
[lists:zipwith(fun(X,Y)->X+Y end,[0]++H,H++[0])|L].
[edit] Factor
This implementation works by summing the previous line content. Result for n < 1 is the same as for n == 1.
USING: grouping kernel math sequences ;
: (pascal) ( seq -- newseq )
dup last 0 prefix 0 suffix 2 <clumps> [ sum ] map suffix ;
: pascal ( n -- seq )
1 - { { 1 } } swap [ (pascal) ] times ;
It works as:
5 pascal .
{ { 1 } { 1 1 } { 1 2 1 } { 1 3 3 1 } { 1 4 6 4 1 } }
[edit] Forth
: init ( n -- )
here swap cells erase 1 here ! ;
: .line ( n -- )
cr here swap 0 do dup @ . cell+ loop drop ;
: next ( n -- )
here swap 1- cells here + do
i @ i cell+ +!
-1 cells +loop ;
: pascal ( n -- )
dup init 1 .line
1 ?do i next i 1+ .line loop ;
This is a bit more efficient. Translation of: C
: PascTriangle
cr dup 0
?do
1 over 1- i - 2* spaces i 1+ 0 ?do dup 4 .r j i - * i 1+ / loop cr drop
loop drop
;
13 PascTriangle
[edit] Fortran
Works with: Fortran version 90 and later Prints nothing for n<=0. Output formatting breaks down for n>20
PROGRAM Pascals_Triangle
CALL Print_Triangle(8)
END PROGRAM Pascals_Triangle
SUBROUTINE Print_Triangle(n)
IMPLICIT NONE
INTEGER, INTENT(IN) :: n
INTEGER :: c, i, j, k, spaces
DO i = 0, n-1
c = 1
spaces = 3 * (n - 1 - i)
DO j = 1, spaces
WRITE(*,"(A)", ADVANCE="NO") " "
END DO
DO k = 0, i
WRITE(*,"(I6)", ADVANCE="NO") c
c = c * (i - k) / (k + 1)
END DO
WRITE(*,*)
END DO
END SUBROUTINE Print_Triangle
[edit] Groovy
[edit] Recursive
In the spirit of the Haskell "think in whole lists" solution here is a list-driven, minimalist solution:
def pascal = { n -> (n <= 1) ? [1] : GroovyCollections.transpose([[0] + pascal(n - 1), pascal(n - 1) + [0]]).collect { it.sum() } }
However, this solution is horribly inefficient (O(n**2)). It slowly grinds to a halt on a reasonably powerful PC after about line 25 of the triangle.
Test program:
def count = 15
(1..count).each { n ->
printf ("%2d:", n); (0..(count-n)).each { print " " }; pascal(n).each{ printf("%6d ", it) }; println ""
}
Output:
1: 1 2: 1 1 3: 1 2 1 4: 1 3 3 1 5: 1 4 6 4 1 6: 1 5 10 10 5 1 7: 1 6 15 20 15 6 1 8: 1 7 21 35 35 21 7 1 9: 1 8 28 56 70 56 28 8 1 10: 1 9 36 84 126 126 84 36 9 1 11: 1 10 45 120 210 252 210 120 45 10 1 12: 1 11 55 165 330 462 462 330 165 55 11 1 13: 1 12 66 220 495 792 924 792 495 220 66 12 1 14: 1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1 15: 1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
[edit] Haskell
An approach using the "think in whole lists" principle: Each row in the triangle can be calculated from the previous row by adding a shifted version of itself to it, keeping the ones at the ends. The Prelude function zipWith can be used to add two lists, but it won't keep the old values when one list is shorter. So we need a similar function
zapWith :: (a -> a -> a) -> [a] -> [a] -> [a]
zapWith f xs [] = xs
zapWith f [] ys = ys
zapWith f (x:xs) (y:ys) = f x y : zapWith f xs ys
Now we can shift a list and add it to itself, extending it by keeping the ends:
extendWith f [] = []
extendWith f xs@(x:ys) = x : zapWith f xs ys
And for the whole (infinite) triangle, we just iterate this operation, starting with the first row:
pascal = iterate (extendWith (+)) [1]
For the first n rows, we just take the first n elements from this list, as in
*Main> take 6 pascal
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
A shorter approach, plagiarized from [1]
-- generate next row from current row
nextRow row = zipWith (+) ([0] ++ row) (row ++ [0])
-- returns the first n rows
pascal = iterate nextRow [1]
[edit] HicEst
CALL Pascal(30)
SUBROUTINE Pascal(rows)
CHARACTER fmt*6
WRITE(Text=fmt, Format='"i", i5.5') 1+rows/4
DO row = 0, rows-1
n = 1
DO k = 0, row
col = rows*(rows-row+2*k)/4
WRITE(Row=row+1, Column=col, F=fmt) n
n = n * (row - k) / (k + 1)
ENDDO
ENDDO
END
[edit] 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
(-@|. |."_1 [: ;:inv [: ":@-.&0&.>@|: !/~)@i. 5
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
See the talk page for explanation
[edit] IDL
Pro Pascal, n
;n is the number of lines of the triangle to be displayed
r=[1]
print, r
for i=0, (n-2) do begin
pascalrow,r
endfor
End
Pro PascalRow, r
for i=0,(n_elements(r)-2) do begin
r[i]=r[i]+r[i+1]
endfor
r= [1, r]
print, r
End
[edit] Java
[edit] Summing from Previous Rows
Works with: Java version 1.5+
import java.util.ArrayList;
...//class definition, etc.
public static void genPyrN(int rows){
if(rows < 0) return;
//save the last row here
ArrayList<Integer> last = new ArrayList<Integer>();
last.add(1);
System.out.println(last);
for(int i= 1;i <= rows;++i){
//work on the next row
ArrayList<Integer> thisRow= new ArrayList<Integer>();
thisRow.add(last.get(0)); //beginning
for(int j= 1;j < i;++j){//loop the number of elements in this row
//sum from the last row
thisRow.add(last.get(j - 1) + last.get(j));
}
thisRow.add(last.get(i)); //end
last= thisRow;//save this row
System.out.println(thisRow);
}
}
[edit] Combinations
This method is limited to 21 rows because of the limits of long. Calling pas with an argument of 22 or above will cause intermediate math to wrap around and give false answers.
public class Pas{
public static void main(String[] args){
//usage
pas(20);
}
public static void pas(int rows){
for(int i = 0; i < rows; i++){
for(int j = 0; j <= i; j++){
System.out.print(ncr(i, j) + " ");
}
System.out.println();
}
}
public static long ncr(int n, int r){
return fact(n) / (fact(r) * fact(n - r));
}
public static long fact(int n){
long ans = 1;
for(int i = 2; i <= n; i++){
ans *= i;
}
return ans;
}
}
[edit] Logo
to pascal :n
if :n = 1 [output [1]]
localmake "a pascal :n-1
output (sentence first :a (map "sum butfirst :a butlast :a) last :a)
end
for [i 1 10] [print pascal :i]
[edit] Lua
function nextrow(t)
local ret = {}
t[0], t[#t+1] = 0, 0
for i = 1, #t do ret[i] = t[i-1] + t[i] end
return ret
end
function triangle(n)
t = {1}
for i = 1, n do
print(unpack(t))
t = nextrow(t)
end
end
[edit] Metafont
(The formatting starts to be less clear when numbers start to have more than two digits)
vardef bincoeff(expr n, k) =
save ?;
? := (1 for i=(max(k,n-k)+1) upto n: * i endfor )
/ (1 for i=2 upto min(k, n-k): * i endfor); ?
enddef;
def pascaltr expr c =
string s_;
for i := 0 upto (c-1):
s_ := "" for k=0 upto (c-i): & " " endfor;
s_ := s_ for k=0 upto i: & decimal(bincoeff(i,k))
& " " if bincoeff(i,k)<9: & " " fi endfor;
message s_;
endfor
enddef;
pascaltr(4);
end
[edit] Nial
Like J
(pascal.nial)
factorial is recur [ 0 =, 1 first, pass, product, -1 +]
combination is fork [ > [first, second], 0 first,
/ [factorial second, * [factorial - [second, first], factorial first] ]
]
pascal is transpose each combination cart [pass, pass] tell
Using it
|loaddefs 'pascal.nial'
|pascal 5
[edit] OCaml
(* generate next row from current row *)
let next_row row =
List.map2 (+) ([0] @ row) (row @ [0])
(* returns the first n rows *)
let pascal n =
let rec loop i row =
if i = n then []
else row :: loop (i+1) (next_row row)
in loop 0 [1]
[edit] Octave
function pascaltriangle(h)
for i = 0:h-1
for k = 0:h-i
printf(" ");
endfor
for j = 0:i
printf("%3d ", bincoeff(i, j));
endfor
printf("\n");
endfor
endfunction
pascaltriangle(4);
[edit] Oz
declare
fun {NextLine Xs}
{List.zip 0|Xs {Append Xs [0]}
fun {$ Left Right}
Left + Right
end}
end
fun {Triangle N}
{List.take {Iterate [1] NextLine} N}
end
fun lazy {Iterate I F}
I|{Iterate {F I} F}
end
%% Only works nicely for N =< 5.
proc {PrintTriangle T}
N = {Length T}
in
for
Line in T
Indent in N-1..0;~1
do
for _ in 1..Indent do {System.printInfo " "} end
for L in Line do {System.printInfo L#" "} end
{System.printInfo "\n"}
end
end
in
{PrintTriangle {Triangle 5}}
For n = 0, prints nothing. For negative n, throws an exception.
[edit] Perl
sub pascal
# Prints out $n rows of Pascal's triangle. It returns undef for
# failure and 1 for success.
{my $n = shift;
$n < 1 and return undef;
print "1\n";
$n == 1 and return 1;
my @last = (1);
foreach my $row (1 .. $n - 1)
{my @this = map {$last[$_] + $last[$_ + 1]} 0 .. $row - 2;
@last = (1, @this, 1);
print join(' ', @last), "\n";}
return 1;}
Here is a shorter version using bignum, which is limited to the first 23 rows because of the algorithm used:
use bignum;
sub pascal { $_[0] ? unpack "A(A6)*", 1000001**$_[0] : 1 }
print "@{[map -+-$_, pascal $_]}\n" for 0..22;
[edit] Perl 6
Translation of: Haskell (the short version)
Works with: Rakudo version #23 "Lisbon"
Nonpositive inputs throw a multiple-dispatch error.
multi pascal (1) { [1] }
multi pascal (Int $n where (* > 1)) {
my @rows = pascal $n - 1;
@rows, [( 0, @(@rows[*-1]) ) >>+<< ( @(@rows[*-1]), 0 )];
}
say .perl for pascal 10;
Translation of: Perl
sub pascal ($n)
# Prints out $n rows of Pascal's triangle.
{$n < 1 and return Mu;
say "1";
$n == 1 and return 1;
my @last = [1];
for (1 .. $n - 1) -> $row
{my @this = map (-> $a {@last[$a] + @last[$a + 1]}), 0 .. $row - 2;
@last = (1, @this, 1);
say join(' ', @last) ;}
return 1;}
The following routine returns a lazy list of lines using the series operator. With a lazy result you need not tell the routine how many you want; you can just use a slice subscript to get the first N lines:
sub pascal { [1], -> @p { [0, @p Z+ @p, 0] } ... * }
.say for pascal[^10];
See http://perlgeek.de/blog-en/perl-6/pascal-triangle.writeback for a partial explanation of how this one-liner example works.
[edit] PHP
function pascalsTriangle($num){
$c = 1;
$triangle = Array();
for($i=1;$i<$num;$i++){
$triangle[$i] = Array();
if(!isset($triangle[$i-1])){
$triangle[$i][] = $c;
}else{
for($j=0;$j<count($triangle[$i-1])+1;$j++){
$triangle[$i][] = (isset($triangle[$i-1][$j-1]) && isset($triangle[$i-1][$j])) ? $triangle[$i-1][$j-1] + $triangle[$i-1][$j] : $c;
}
}
}
return $triangle;
}
$tria = pascalsTriangle(10);
foreach($tria as $val){
foreach($val as $value){
echo $value . ' ';
}
echo '<br>';
}
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
[edit] PL/I
declare (t, u)(40) fixed binary;
declare (i, n) fixed binary;
t,u = 0;
get (n);
if n <= 0 then return;
do n = 1 to n;
u(1) = 1;
do i = 1 to n;
u(i+1) = t(i) + t(i+1);
end;
put skip edit ((u(i) do i = 1 to n)) (col(40-2*n), (n+1) f(4));
t = u;
end;
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
[edit] PicoLisp
Translation of: C
(de pascalTriangle (N)
(for I N
(space (* 2 (- N I)))
(let C 1
(for K I
(prin (align 3 C) " ")
(setq C (*/ C (- I K) K)) ) )
(prinl) ) )
[edit] PureBasic
Procedure pascaltriangle( n.i)
For i= 0 To n
c = 1
For k=0 To i
Print(Str( c)+" ")
c = c * (i-k)/(k+1);
Next ;k
PrintN(" "); nächste zeile
Next ;i
EndProcedure
OpenConsole()
Parameter.i = Val(ProgramParameter(0))
pascaltriangle(Parameter);
Input()
[edit] Python
def pascal(n):
"""Prints out n rows of Pascal's triangle.
It returns False for failure and True for success."""
row = [1,]
k = [0,]
for x in range(max(n,0)):
print row
row=[l+r for l,r in zip(row+k,k+row)]
return n>=1
[edit] R
Translation of: Octave
pascalTriangle <- function(h) {
for(i in 0:(h-1)) {
s <- ""
for(k in 0:(h-i)) s <- paste(s, " ", sep="")
for(j in 0:i) {
s <- paste(s, sprintf("%3d ", choose(i, j)), sep="")
}
print(s)
}
}
Here's an R version:
pascalTriangle <- function(h) {
lapply(0:h, function(i) choose(i, 0:i))
}
[edit] RapidQ
[edit] Summing from Previous Rows
Translation of: BASIC
The main difference to BASIC implementation is the output formatting. RapidQ does not support PRINT USING. Instead, function FORMAT$() is used. TAB() is not supported, so SPACE$() was used instead.
Another difference is that in RapidQ, DIM does not clear array values to zero. But if dimensioning is done with DEF..., you can give the initial values in curly braces. If less values are given than there are elements in the array, the remaining positions are initialized to zero. RapidQ does not require simple variables to be declared before use.
DEFINT values(100) = {0,1}
INPUT "Number of rows: "; nrows
PRINT SPACE$((nrows)*3);" 1"
FOR row = 2 TO nrows
PRINT SPACE$((nrows-row)*3+1);
FOR i = row TO 1 STEP -1
values(i) = values(i) + values(i-1)
PRINT FORMAT$("%5d ", values(i));
NEXT i
PRINT
NEXT row
[edit] Using binary coefficients
Translation of: BASIC
INPUT "Number of rows: "; nrows
FOR row = 0 TO nrows-1
c = 1
PRINT SPACE$((nrows-row)*3);
FOR i = 0 TO row
PRINT FORMAT$("%5d ", c);
c = c * (row - i) / (i+1)
NEXT i
NEXT row
[edit] Ruby
def pascal(n = 1)
return if n < 1
# set up a new array of arrays with the first value
p = [[1]]
# for n - 1 number of times,
(n - 1).times do |i|
# inject a new array starting with [1]
p << p[i].inject([1]) do |result, elem|
# if we've reached the end, tack on a 1.
# else, tack on current elem + previous elem
if p[i].length == result.length
result << 1
else
result << elem + p[i][result.length]
end
end
end
# and return the triangle.
p
end
Or for more or less a translation of the two line Haskell version (with inject being abused a bit I know):
def next_row row ; ([0] + row).zip(row + [0]).collect {|l,r| l + r }; end
def pascal n ; ([nil] * n).inject([1]) {|x,y| y = next_row x } ; end
[edit] Scala
Simple recursive row definition:
def tri(row:Int):List[Int] = { row match {
case 1 => List(1)
case n:Int => List(1) ::: ((tri(n-1) zip tri(n-1).tail) map {case (a,b) => a+b}) ::: List(1)
}
}
Funtion to pretty print n rows:
def prettytri(n:Int) = (1 to n) foreach {i=>print(" "*(n-i)); tri(i) map (c=>print(c+" ")); println}
prettytri(5)
Outputs:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
[edit] Scheme
Works with: Scheme version R5RS
(define (next-row row)
(map + (append (list 0) row) (append row (list 0))))
(define (triangle row rows)
(if (= rows 0)
(list)
(cons row (triangle (next-row row) (- rows 1)))))
(display (triangle (list 1) 5))
(newline)
Output:
((1) (1 1) (1 2 1) (1 3 3 1) (1 4 6 4 1))
[edit] Seed7
$ include "seed7_05.s7i";
const proc: main is func
local
var integer: numRows is 0;
var array integer: values is [] (0, 1);
var integer: row is 0;
var integer: index is 0;
begin
write("Number of rows: ");
readln(numRows);
writeln("1" lpad succ(numRows) * 3);
for row range 2 to numRows do
write("" lpad (numRows - row) * 3);
values &:= [] 0;
for index range succ(row) downto 2 do
values[index] +:= values[pred(index)];
write(" " <& values[index] lpad 5);
end for;
writeln;
end for;
end func;
[edit] Tcl
[edit] Summing from Previous Rows
proc pascal_iterative n {
if {$n < 1} {error "undefined behaviour for n < 1"}
set row [list 1]
lappend rows $row
set i 1
while {[incr i] <= $n} {
set prev $row
set row [list 1]
for {set j 1} {$j < [llength $prev]} {incr j} {
lappend row [expr {[lindex $prev [expr {$j - 1}]] + [lindex $prev $j]}]
}
lappend row 1
lappend rows $row
}
return $rows
}
puts [join [pascal_iterative 6] \n]
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1
[edit] Using binary coefficients
Translation of: BASIC
proc pascal_coefficients n {
if {$n < 1} {error "undefined behaviour for n < 1"}
for {set i 0} {$i < $n} {incr i} {
set c 1
set row [list $c]
for {set j 0} {$j < $i} {incr j} {
set c [expr {$c * ($i - $j) / ($j + 1)}]
lappend row $c
}
lappend rows $row
}
return $rows
}
puts [join [pascal_coefficients 6] \n]
[edit] Combinations
Translation of: Java, however thanks to Tcl 8.5's arbitrary precision integer arithmetic, this solution is not limited to a couple of dozen rows. Uses a caching factorial calculator to improve performance.
package require Tcl 8.5
proc pascal_combinations n {
if {$n < 1} {error "undefined behaviour for n < 1"}
for {set i 0} {$i < $n} {incr i} {
set row [list]
for {set j 0} {$j <= $i} {incr j} {
lappend row [C $i $j]
}
lappend rows $row
}
return $rows
}
proc C {n k} {
expr {[ifact $n] / ([ifact $k] * [ifact [expr {$n - $k}]])}
}
set fact_cache {1 1}
proc ifact n {
global fact_cache
if {$n < [llength $fact_cache]} {
return [lindex $fact_cache $n]
}
set i [expr {[llength $fact_cache] - 1}]
set sum [lindex $fact_cache $i]
while {$i < $n} {
incr i
set sum [expr {$sum * $i}]
lappend fact_cache $sum
}
return $sum
}
puts [join [pascal_combinations 6] \n]
[edit] Comparing Performance
set n 100
puts "calculate $n rows:"
foreach proc {pascal_iterative pascal_coefficients pascal_combinations} {
puts "$proc: [time [list $proc $n] 100]"
}
outputs
calculate 100 rows: pascal_iterative: 2800.14 microseconds per iteration pascal_coefficients: 8760.98 microseconds per iteration pascal_combinations: 38176.66 microseconds per iteration
[edit] Ursala
Zero maps to the empty list. Negatives are inexpressible. This solution uses a library function for binomial coefficients.
#import std
#import nat
pascal = choose**ziDS+ iota*t+ iota+ successor
This solution uses direct summation. The algorithm is to insert zero at the head of a list (initially the unit list <1>), zip it with its reversal, map the sum over the list of pairs, iterate n times, and return the trace.
#import std
#import nat
pascal "n" = (next"n" sum*NiCixp) <1>
test program:
#cast %nLL
example = pascal 10
output:
< <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>>
[edit] Vedit macro language
[edit] Summing from Previous Rows
Translation of: BASIC
Vedit macro language does not have actual arrays (edit buffers are normally used for storing larger amounts of data). However, a numeric register can be used as index to access another numeric register. For example, if #99 contains value 2, then #@99 accesses contents of numeric register #2.
#100 = Get_Num("Number of rows: ", STATLINE)
#0=0; #1=1
Ins_Char(' ', COUNT, #100*3-2) Num_Ins(1)
for (#99 = 2; #99 <= #100; #99++) {
Ins_Char(' ', COUNT, (#100-#99)*3)
#@99 = 0
for (#98 = #99; #98 > 0; #98--) {
#97 = #98-1
#@98 += #@97
Num_Ins(#@98, COUNT, 6)
}
Ins_Newline
}
[edit] Using binary coefficients
Translation of: BASIC
#1 = Get_Num("Number of rows: ", STATLINE)
for (#2 = 0; #2 < #1; #2++) {
#3 = 1
Ins_Char(' ', COUNT, (#1-#2-1)*3)
for (#4 = 0; #4 <= #2; #4++) {
Num_Ins(#3, COUNT, 6)
#3 = #3 * (#2-#4) / (#4+1)
}
Ins_Newline
}
