Trees with Labeled Nodes that form Permutation of Positive Integers

[franktaw at netscape.net]

I don't know Maple well enough - or have enough time - to tell: does 
this keep each path separately, or does it keep a count of the number 
of paths with a given set of integers on the path?

The latter approach should be much faster and less memory intensive, 
once you get past the first few generations.  (Probably still 
exponential, though.)

Franklin T. Adams-Watters

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

...

Maple V:

gen := proc(parents,maxgen,ocounts,lvl)
    local thislbl,lbl,childlbl,counts,npar ;
    counts := ocounts ;
    counts[lvl] := counts[lvl]+1 ;
    if nops(parents) < maxgen then
        thislbl := op(-1,parents) ;
        childlbl := 1 ;
        for lbl from 1 to thislbl do
            while ( childlbl in parents ) or ( childlbl = thislbl ) do
                childlbl := childlbl+1 ;
            od ;
            npar := [op(parents),childlbl] ;
            # this would generate a full list of all paths:
            # print("route",npar) ;
            if nops(counts) < lvl+1 then
                counts := [op(counts),0] ;
            fi ;
            counts := gen(npar,maxgen,counts,lvl+1) ;
            childlbl := childlbl+1 ;
        od ;
    fi ;
    # this produces a snapshot of the counts accumulated so far:
    # if the current node creation level is not too high, print it...
    if lvl <= maxgen -3 then
        print(counts) ;
    fi ;
    RETURN(counts) ;
end:

# Edit the maximum number below...total run time probably grows 
exponentially
# with the number chosen here.
maxgen := 8 ;
parents := [1,2] ;
n := [1,0] ;
gen(parents,maxgen,n,2) ;
print(%) ;

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