#RandTree(A,k) generates a random tree in alphabet A with depth k.

#The format is the original format you suggested in classs where a leaf is
#denoted by only the edge leading into it, rather than [edge,[]] like Avi's
#format.

#-Baxter

with(combinat):

#RandTree(A,k) given alphabet A and integer k outputs a random tree of maximum depth k
RandTree:=proc(A,k) local ra,nuch,i,S,T,T1:

ra:=rand(1..nops(A)):

if k=0 then
 nuch:=ra():
 S:=choose(A,nuch):
 S:=S[rand(1..nops(S))()]:
 
 T:=[]: 

 for i from 1 to nuch do
  T1:=S[i];
  T:=[op(T),T1]:
 od:
RETURN(T):
fi:

nuch:=ra():

S:=choose(A,nuch):
S:=S[rand(1..nops(S))()]:

T:=[]:

for i from 1 to nuch do
 T1:=[S[i],RandTree(A,rand(0..k-1)())];
 T:=[op(T),T1]:
od:

T:
end: