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

[franktaw at netscape.net]

No hashing is necessary.  There are (n-1)! possible sets of labels.  
Each
sorted sequence of labels has an increase of at most k between the kth
and k+1st label.  So you can take the first differences, subtract 1,
reverse, and treat as a base factorial number.  E.g., for 1,2,4,5,9, 
the
differences are 1,2,1,4; subtract one and reverse to get 3010,
3*3!+0*2!+1*1! = 19, so this will be at (zero-based) index 19.  (This 
is
easily reversible to get the label set from the index and level.)

For each label set, you'll need to keep a count of how many nodes
there are with each possible final label, to tell what to generate in
the next level.  Since 1 and 2 can't be labels after level 2, you only
need to keep n-2 such counters for each set.

We can tell that this algorithm is on the order of n! to compute level 
n.
The naive approach is proportional to the size of the nth level, which 
is
certainly greater; since the largest term at level n is C(n,2)+1 ~ 
n^2/2,
it is certainly no more than (n^2/2)!.  I'm guessing that is it more 
like
c^n n!, for some c between 1.6 and 2 (probably closer to 2, from the
data, though convergence is slow; k 2^n n!/n^2 gives a fairly good
fit to the available data).

Based on this, the eventual savings should be much larger than merely
switching to a compiled language.  I'll also leave this as an exercise,
though. :-)

Franklin T. Adams-Watters


-----Original Message-----
From: mathar at strw.leidenuniv.nl

ftaw> From seqfan-owner at ext.jussieu.fr  Thu Nov 16 19:01:33 2006
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

________________________________________________________________________
Check Out the new free AIM(R) Mail -- 2 GB of storage and 
industry-leading spam and email virus protection.