extra/rosetta-code/pascals-triangle/pascals-triangle.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: grouping kernel math ranges sequences ;
   4 IN: rosetta-code.pascals-triangle
   5
   6 ! http://rosettacode.org/wiki/Pascal%27s_triangle
   7
   8 ! Pascal's triangle is an interesting math concept. Its first few rows look like this:
   9 !    1
  10 !   1 1
  11 !  1 2 1
  12 ! 1 3 3 1
  13
  14 ! where each element of each row is either 1 or the sum of the
  15 ! two elements right above it. For example, the next row would be
  16 ! 1 (since the first element of each row doesn't have two elements
  17 ! above it), 4 (1 + 3), 6 (3 + 3), 4 (3 + 1), and 1 (since the
  18 ! last element of each row doesn't have two elements above it).
  19 ! Each row n (starting with row 0 at the top) shows the
  20 ! coefficients of the binomial expansion of (x + y)n.
  21
  22 ! Write a function that prints out the first n rows of the
  23 ! triangle (with f(1) yielding the row consisting of only the
  24 ! element 1). This can be done either by summing elements from the
  25 ! previous rows or using a binary coefficient or combination
  26 ! function. Behavior for n <= 0 does not need to be uniform, but
  27 ! should be noted.
  28
  29 :: pascal-coefficients ( n -- seq )
  30     1 n [1..b] [
  31         dupd [ n swap - * ] [ /i ] bi swap
  32     ] map nip ;
  33
  34 : (pascal) ( seq -- newseq )
  35     dup last 0 prefix 0 suffix 2 <clumps> [ sum ] map suffix ;
  36
  37 : pascal ( n -- seq )
  38     1 - { { 1 } } swap [ (pascal) ] times ;