#OK to post homework
#George Spahn, 4/25/2021, Assignment 25


# HookSet(L,cell) Inputs a shape L and a cell [i,j], 
# with 1≤ i ≤nops(L), 1 ≤ j ≤ L[i], 
# and outputs set set of all cells that are (weakly) to the right in the 
# same row, and (weakly) down in the same column. For example,
# HookSet([5,5,3,2,1],[2,2]);
# should output the set {[2,2],[2,3],[2,4],[2,5],[3,2],[4,2]}

HookSet:=proc(L,cell) local i:

for i from cell[1] to nops(L) while L[i] >= cell[2] do od:

{seq([cell[1],j], j = cell[2]..L[cell[1]] )} union 
{seq([j,cell[2]], j = cell[1]..i-1 )} :
end:



# OneStepGNW(L)

OneStepGNW:=proc(L) local r,i,hs:

randomize():
r:=rand(1..add(L))():
for i from 1 to nops(L) do
 if r > L[i] then
  r:=r-L[i]:
 else
  break:
 fi:
od:
while r < L[i] or (i < nops(L) and L[i+1] >= r) do
 hs:=HookSet(L,[i,r]) minus {[i,r]}:
 i,r:=op(hs[rand(1..nops(hs))()]):
od:
i,r:
end:

#GNW(L)
GNW:=proc(L) local i,j,newL,rec:

if L= [] then
 RETURN([]):
fi:
i,j:=OneStepGNW(L):

if j > 1 then
 newL:=L:
 newL[i]:=newL[i]-1:
 rec:=GNW(newL):
 rec[i]:=[op(rec[i]),add(L)]:
else
 newL:=[op(1..nops(L)-1,L)]:
 rec:=[op(GNW(newL)),[add(L)]]:
fi:
rec:
end: