#March 4, 2013 Gambling (binary trees)

Help:=proc(): print(` BT(n) , NuL(T) , DressUp(T,L) `): 
print(` C(n), RollLD(L) , RandBT(n) `):
end:

#BT(n): The set of all fulll binary trees
#every vertex has either TWO children or ZERO children
#(then it is called a leaf)
#with n leaves, in  the format
#Tree=[] or [T1,T2] (T1 and T2 are smaller trees)
BT:=proc(n) local k, S, S1,S2,t1,t2:
option remember:

if n=0 then
RETURN({}):
fi:

if n=1 then
 RETURN({ [ ] }):
fi:

S:={}:

for k from 1 to n-1 do
 S1:=BT(k):
 S2:=BT(n-k):
 S:=S union {seq(seq([t1,t2], t1 in S1), t2 in S2)}:
od:

S:

end:

#NuL(T): the number of leaves of T
NuL:=proc(T) option remember:

if T=[] then
  1:
else
  NuL(T[1])+NuL(T[2]):
fi:

end:




#DressUp(T,L): inputs a "naked" binary tree with
#n (say) leaves and a list of numbers and
#sticks the numbers in order from left to right
#For example
#DressUp([[],[[],[]]],[4,1,3]);
#should be [[4],[[1],[3]]]
DressUp:=proc(T,L) local k, T1, T2:

if nops(L)<>NuL(T) then
 RETURN(FAIL):
fi:

if nops(L)=1 then
 RETURN([L[1]]):
#wise-guy Jacob Baron claims (mathematically correctly
#but morally incorrectly) that [L[1]] is the same L
fi:

k:=NuL(T[1]):

T1:=DressUp(T[1],[op(1..k,L)]):

T2:=DressUp(T[2],[op(k+1..nops(L),L)]):

[ T1, T2]:
end:

#C(n): the number of full binary trees with n leaves
C:=proc(n) local k:
option remember:

if n=1 then
1:
else
 add(C(k)*C(n-k), k=1..n-1):
fi:

end:

#RollLD(L): inputs a list of NON-NEGATIVE
#integers and outputs an integer from 1
#nops(L) such that the prob. of getting i
#is L[i]/convert(L,`+`):

RollLD:=proc(L) local Tot,ra,j,i,m :

Tot:=convert(L,`+`):

j:=rand(1..Tot)():

for i from 1 to nops(L) while add(L[m],m=1..i)<j do od:
i:

end:

#RollLDTomasPrettyGood(L): inputs a list of NON-NEGATIVE
#integers and outputs an integer from 1
#nops(L) such that the prob. of getting i
#is L[i]/convert(L,`+`):
#Brilliant version of Tomas Vyskocil
RollLDPrettyGood:=proc(L) local N:
	N := [seq(i$L[i], i=1..nops(L))]:
	return N[rand(1..nops(N))()]:
end:


#RandBT(n): A uniformly random full buinary 
#tree with n leaves
RandBT:=proc(n) local L,k,i:

if n=1 then
  RETURN([]):
fi:

i:=RollLD([seq(C(k)*C(n-k), k=1..n-1)]):

[RandBT(i),RandBT(n-i)]:

end: