#OK to post homework
#Wanying Rao, 05/02/2021, Assignment 26

#2
StartShape := proc(Y,k) local S,i,j:

S := []:

for i from 1 to nops(Y) do
 j := 1:
 while j<=nops(Y[i]) and Y[i][j]<=k do
  j := j+1:
 od:
 j := j-1:
 if j <> 0 then
  S := [op(S),j]:
 fi:
od:

S:
end:

#3
EstStart := proc(L,k,K) local S,P,i,p,n,j:

S := Pn(k):
P := []:
p := []:
for i from 1 to K do
 P := [op(P),StartShape(GNW(L),k)]:
od:

for i from 1 to nops(S) do
 n := 0:
 for j from 1 to K do
  if P[j] = S[i] then
   n := n+1:
  fi:
 od:
 p := [op(p),n/K]:
od:

p:
end:


#From hw25
#1
HookSet := proc(L,cell) local i,S,R,D,m:

if not cell[1]>=1 and cell[1]<=nops(L) and cell[2]>=1 and cell[2]<=L[cell[1]] then
 RETURN(FAIL):
fi:

S := {cell}:

R := {seq([cell[1],i],i=cell[2]+1..L[cell[1]])}:

m := nops(L):
while L[m] < cell[2] do
m := m-1:
od:

D := {seq([j,cell[2]],j=cell[1]+1..m)}:

S union R union D:
end:

#2
OneStepGNW := proc(L) local n,r,Y,cell,H:

n := add(L):
cell := [1,1]:
while nops(HookSet(L,cell))<>1 do
 H := HookSet(L,cell) minus {cell}:
 r := rand(1..nops(H))():
 cell := H[r]:
od:

cell:
end:

#3
GNW := proc(L) local cell,n,L1,Y1,Y:

n := add(L):

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

cell := OneStepGNW(L):
L1 := L:
L1[cell[1]] := L1[cell[1]]-1:
Y1 := GNW(L1):

if cell[1] <= nops(Y1) then
 Y := [op(1..cell[1]-1,Y1),[op(Y1[cell[1]]),n],op(cell[1]+1..nops(Y1),Y1)]:
fi:
if cell[1] = nops(Y1)+1 then
 Y := [op(1..cell[1]-1,Y1),[n]]:
fi:

Y:
end:

#From C11.txt
#Pnk(n,k): The LIST of integer partitions of n with largest part k
Pnk:=proc(n,k) local k1,L,L1:
option remember:

if not (type(n,integer) and type(k,integer) and n>=1 and k>=1 )then
 RETURN([]):
fi:
 
if k>n then
 RETURN([]):
fi:

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

L:=[]:

for k1 from min(n-k,k) by -1 to 1 do
 L1:=Pnk(n-k,k1):
 L:=[op(L), seq([k, op(L1[j])],j=1..nops(L1))]:
od:

L:

end:

#Pn(n): The list of integer partitions of n in rev. lex. order
Pn:=proc(n) local k:option remember:[seq(op(Pnk(n,n-k+1)),k=1..n)]:end: