extra/rosetta-code/catalan-numbers/catalan-numbers.factor

   1 ! Copyright (c) 2012 Anonymous
   2 ! See https://factorcode.org/license.txt for BSD license.
   3 USING: kernel math sequences ;
   4 IN: rosetta-code.catalan-numbers
   5
   6 ! https://rosettacode.org/wiki/Catalan_numbers
   7
   8 ! Catalan numbers are a sequence of numbers which can be defined
   9 ! directly:
  10 !     Cn = 1/(n+1)(2n n) = (2n)! / (n+1)! * n!      for n >= 0
  11
  12 ! Or recursively:
  13 !     C0 = 1
  14 !     Cn+1 = sum(Ci * Cn-i)) {0..n}                 for n >= 0
  15
  16 ! Or alternatively (also recursive):
  17 !     C0 = 1
  18 !     Cn = (2 * (2n - 1) / (n + 1)) * Cn-1
  19
  20 ! Implement at least one of these algorithms and print out the
  21 ! first 15 Catalan numbers with each. Memoization is not required,
  22 ! but may be worth the effort when using the second method above.
  23
  24 : next ( seq -- newseq )
  25     [ ] [ last ] [ length ] tri
  26     [ 2 * 1 - 2 * ] [ 1 + ] bi /
  27     * suffix ;
  28
  29 : catalan ( n -- seq )
  30     V{ 1 } swap 1 - [ next ] times ;