growing binary trees

[Simon Strandgaard]

On 11/12/06, N. J. A. Sloane <njas at research.att.com> wrote:
> I will add Simon S.'s sequence to the OEIS - it will be A123015
> in a few minutes
>
> Can Ruby lines be combined onto one line?


I cannot express this thing as math, and its difficult for me to
compact the code without loss of readability.


below is a 5 line version:

class Node; def initialize; @n = 1; @c = [] end
def count; @c.inject(@n){|n,c| n + c.count} end
def grow; return @n += 1 if @n < 3; @c.each{|c| c.grow }
@c << Node.new if @c.size < 2; end; end; r = []; node = Node.new
30.times { r << node.count; node.grow }; p r


here is the oneliner (less readable):

class C;def initialize;@n=1;@c=[] end;def n;@c.inject(@n){|n,c|n+c.n}
end;def g;return @n+=1 if @n<3; @c.each{|c|c.g};@c<<C.new if
@c.size<2;end;end;r=[];c=C.new;30.times{r<<c.n;c.g};p r



the n-th term is:
a(0)=1, a(1)=2, a(2)=3, a(3)=4, a(4)=6, a(5)=8, a(6)=10, a(7)=13, ...


code for n'th term is below:

class Node
 def initialize
   @n = 1
   @childs = []
 end
 def count
   @childs.inject(@n){|n,child| n + child.count}
 end
 def grow
   return @n += 1 if @n < 3
   @childs.each{|child| child.grow }
   @childs << Node.new if @childs.size < 2
 end
end

def a(n)
  node = Node.new
  n.times{ node.grow }
  node.count
end

0.upto(30) {|n| p a(n) }



visually it works like this:

step#0
  1


step#1
  2


step#2
  3


step#3
  3
 /
1


step#4
  3
 / \
2   1


step#5
  3
 / \
3   2


step#6
    3
   / \
  3   3
 /
1


step#7
      3
    /   \
  3       3
 / \     /
2   1   1


step#8
      3
    /   \
  3       3
 / \     / \
3   2   2   1



--
Simon Strandgaard