# Ok to post homework
# Lucy Martinez, 02-14-2025, Assignment 7

with(combinat):

######################

# Problem 2: Write a procedure NumberOfLeaves(T)
#  that inputs a labeled tree, T, and outputs the number of leaves
#  (vertices of degree 1).
#  For example NumberOfLeaves({{1,2},{1,3},{1,4}}); should output 3
NumberOfLeaves:=proc(T) local L,e,N,V,v:
V:={seq(op(e), e in T)}:
for v in V do
 N[v]:={}:
od:

for e in T do
 N[e[1]]:=N[e[1]] union {e[2]}:
 N[e[2]]:=N[e[2]] union {e[1]}:
od:

#L will contain all leafs
L:={}:
#look at all vertices, we want to find out whether v is a leaf or not
for v in V do
 if nops(N[v])=1 then
  L:=L union {v}:
 fi:
od:
nops(L):
end:



# Problem 3: Write a procedure RandomTree(n)
#  that inputs a positive integer n, and outputs a random labeled tree
#  on {1, ...,n}
#  [Hint: using rand(1..n), generate a random list of length n-2, P,
#  and then let T:=AntiPC(P)]
RandomTree:=proc(n) local ra,P,i,T:
ra:=rand(1..n):
P:=[seq(ra(),i=1..n-2)]:
T:=AntiPC(P):
T:
end:



# Problem 4: Write a procedure EstimateAverageNumberOfLeaves(n,K)
#  that uses simulation to estimate the average number of leaves
#  in a random labeled tree with n vertices
#  [Hint: run RandomTree(n) K times, for each time find out the number of leaves,
#  add them all up and divide by K.]

#  What did you get for
#  EstimateAverageNumberOfLeaves(100,1000)? 
#   Answer: 37.30900000
#  EstimateAverageNumberOfLeaves(100,10000)?
#   Answer: 37.36420000
#  Are they close? Yes, they are!

EstimateAverageNumberOfLeaves:=proc(n,K) local i,leaves,T:
leaves:=0:
for i from 1 to K do
 T:=RandomTree(n):
 leaves:=leaves+NumberOfLeaves(T):
od:
evalf(leaves/K):
end:




######################################Previous classes:

#C7.txt, Feb. 13, 2025
Help7:=proc():
print(`PC1(T), PC(T), AntiPC1(V,a,T1), AntiPC(P)`):
end:

#WikiTree
WT:={{1,4},{2,4},{3,4},{4,5},{5,6}}:


#PC1(T): One step in the Prufer code algorithm. Looks for the smallest leaf
# outputs the pair [a,T1] where a is the LABEL of the (only) neighbor of
# the smallest leaf (leaf with smallest label) and T1 is the smaller tree
# where only the edge incident to that leaf is removed
PC1:=proc(T) local e,V,N,v,L,a:
V:={seq(op(e), e in T)}:
for v in V do
 N[v]:={}:
od:

for e in T do
 N[e[1]]:=N[e[1]] union {e[2]}:
 N[e[2]]:=N[e[2]] union {e[1]}:
od:

#L will contain all leafs
L:={}:
#look at all vertices, we want to find out whether v is a leaf or not
for v in V do
 if nops(N[v])=1 then
  L:=L union {v}:
 fi:
od:
a:=min(L):
[N[a][1],T minus {{a,N[a][1]}}]:
end:


#PC(T): returns the Prufer sequence of length n-2 of the given tree T
PC:=proc(T) local n, P,i,T1, nick:
#if T is a good tree then there should be |E|+1 vertices
n:=nops(T)+1:
T1:=T:
P:=[]:
for i from 1 to n-2 do
 nick:=PC1(T1):
 P:=[op(P), nick[1]]:
 T1:=nick[2]:
od:
P:
end:


#AntiPC1(V,a,T1): inputs a set of labels (V) for the bigger tree (T)
# to be reconstructed and the current smaller tree T1, finds the label
# of the deleted leaf and appends the edge connecting it to "a"
AntiPC1:=proc(V,a,T1) local e, V1,DL:
V1:={seq(op(e),e in T1)}:
#DL: deleted leaf
DL:=V minus V1:
DL:=DL[1]:
T1 union {{a,DL}}:
end:




#Added after class (based on Nick Belov's idea and top of p. 49 of Robin Wilson's book)

#AntiPC(P): inputs a list of length n-2 with entries from {1, ...,n} outputs the tree with
#labels {1, ...,n} whose Pruffer code is P
AntiPC:=proc(P) local n,V,i,P1,b1,E:
n:=nops(P)+2:
V:={seq(i,i=1..n)}:
P1:=P:
E:={}:
while P1<>[] do
 b1:=min (V minus convert(P1,set)):
 E:=E union {{P1[1],b1}}:
 P1:=[op(2..nops(P1),P1)]:
 V:=V minus {b1}:
od:
E union {V}:
end: