#Nathan Fox
#Homework 12
#I give permission for this file to be posted online

##Read old files
read(`C12.txt`):

#Help procedure
Help:=proc():
print(` Tn(n) , C3(n) , RandTT(n) , SumN3odd(n) `):
print(` Weightlist(n) , RandBTG(n,a) `):
end:

##Problem 1
#Tn(n): inputs a positive integer n and outputs the set of
#all full ternary trees with n leaves, where a vertex can
#either have no children, or exactly three children.
Tn:=proc(n) local S1,S2,S3,k1,k2,S,t1,t2,t3:
option remember:

if n=0 or n=2 then
    return {}:
fi:

if n=1 then
    return {[]}:
fi:

S:={}:

for k1 from 1 to n-2 do
    for k2 from 1 to n-k1-1 do
        S1:=Tn(k1):
        S2:=Tn(k2):
        S3:=Tn(n-k1-k2):
     
        S:=S union {seq(seq(seq([t1,t2,t3],
            t1 in S1), t2 in S2), t3 in S3)}:
    od:
od:

S:

end:

##Problem 2
#C3(n): the number of full ternary trees with n leaves
C3:=proc(n) local k1,k2:
option remember:

if n=1 then
    1:
else
    add(add(C3(k1)*C3(k2)*C3(n-k1-k2),k2=1..n-k1-1),k1=1..n-2):
fi:

end:

##Problem 3
#RandTT(n): A uniformly random full ternary tree with n leaves
RandTT:=proc(n) local L,W,i:

if n=1 then
    return []:
elif (n mod 2)=0 then
    return FAIL:
fi:

L:=SumN3odd(n):
W:=Weightlist(L):

i:=RollLD(W):

[RandTT(L[i][1]),RandTT(L[i][2]),RandTT(L[i][3])]:

end:

#SumN3odd(n): A list of all triples of positive odd integers
#that sum to n
SumN3odd:=proc(n) local k1,k2,ret:

if (n mod 2)=0 then
    return FAIL:
fi:

ret:=[]:

for k1 from 1 to n-2 by 2 do
    for k2 from 1 to n-k1-1 by 2 do
        ret:=[op(ret),[k1,k2,n-k1-k2]]:
    od:
od:

ret:

end:

#Weightlist(L): A list of weights of triples in L
Weightlist:=proc(L) local tpl,ret:

ret:=[]:

for tpl in L do:
    ret:=[op(ret), C3(tpl[1])*C3(tpl[2])*C3(tpl[3])]:
od:

ret:

end:

##Problem 4
#RandBTG(n,a): inputs a positive integer n and a positive
#integer a, and outputs a random gambling tree with n leaves
#where the values at the leaves are integers between 1 and a,
#drawn independently and uniformly at random.
RandBTG:=proc(n,a) local i,ra:

ra:=rand(1..a):

DressUp(RandBT(n),[seq(ra(),i=1..n)]):

end: