Re^2: Trees with Labeled Nodes that form Permutation of Positive Integers

[Richard Mathar]

ftaw> From seqfan-owner at ext.jussieu.fr  Thu Nov 16 19:01:33 2006
ftaw> Return-Path: <seqfan-owner at ext.jussieu.fr>
ftaw> To: seqfan at ext.jussieu.fr
ftaw> Subject: Re: Trees with Labeled Nodes that form Permutation of Positive Integers
ftaw> 
ftaw> I don't know Maple well enough - or have enough time - to tell: does 
ftaw> this keep each path separately, or does it keep a count of the number 
ftaw> of paths with a given set of integers on the path?
ftaw> 
ftaw> The latter approach should be much faster and less memory intensive, 
ftaw> once you get past the first few generations.  (Probably still 
ftaw> exponential, though.)
ftaw> 
ftaw> Franklin T. Adams-Watters
ftaw> 

There is no such optimization in the program shown below. For each
node, it descends into all branches/leafs independent of whether the
set of labels in the current node and higher up in the trunk is the same
or not the same as any set seen earlier. The state vector is
only the vector of counts (one number per generation) which is updated
at each level of recursion, and the single list of labels of the
ancestors of the current node.
So yes, there is room for optimization by introducing some memory
in here, certainly at the cost of increasing the machine memory requirement
to remember all the sub-counts of partial tree in some hash area.

The first action to become faster is to return to a compiled language.
Since this here does not involve any type of functionality which needs a number
theoretic package, one would try to exploit the fact that C would typically be a
factor of 5 to 10 faster than Maple. I don't want to appear selfish and
will therefore leave all this as an exercise to others :-)

RJM

rjm> -----Original Message-----
rjm> From: mathar at strw.leidenuniv.nl
rjm> 
rjm> ...
rjm> 
rjm> Maple V:
rjm> 
rjm> gen := proc(parents,maxgen,ocounts,lvl)
rjm>     local thislbl,lbl,childlbl,counts,npar ;
rjm>     counts := ocounts ;
rjm>     counts[lvl] := counts[lvl]+1 ;
rjm>     if nops(parents) < maxgen then
rjm>         thislbl := op(-1,parents) ;
rjm>         childlbl := 1 ;
rjm>         for lbl from 1 to thislbl do
rjm>             while ( childlbl in parents ) or ( childlbl = thislbl ) do
rjm>                 childlbl := childlbl+1 ;
rjm>             od ;
rjm>             npar := [op(parents),childlbl] ;
rjm>             # this would generate a full list of all paths:
rjm>             # print("route",npar) ;
rjm>             if nops(counts) < lvl+1 then
rjm>                 counts := [op(counts),0] ;
rjm>             fi ;
rjm>             counts := gen(npar,maxgen,counts,lvl+1) ;
rjm>             childlbl := childlbl+1 ;
rjm>         od ;
rjm>     fi ;
rjm>     # this produces a snapshot of the counts accumulated so far:
rjm>     # if the current node creation level is not too high, print it...
rjm>     if lvl <= maxgen -3 then
rjm>         print(counts) ;
rjm>     fi ;
rjm>     RETURN(counts) ;
rjm> end:
rjm> 
rjm> # Edit the maximum number below...total run time probably grows 
rjm> exponentially
rjm> # with the number chosen here.
rjm> maxgen := 8 ;
rjm> parents := [1,2] ;
rjm> n := [1,0] ;
rjm> gen(parents,maxgen,n,2) ;
rjm> print(%) ;