######################################################################
##ParkingPollak.txt: Save this file as  ParkingPollak.txt            #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read ParkingPollak.txt<Enter>                      #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#DoronZeil at gmail dot com                                          #
######################################################################
 
#Created: Jan. 15, 2019
 
print(`Created:  Jan. 15, 2019`):
print(` This is ParkingPollak.txt `):
print(`To illustrate Henry Pollak's slick proof of the fact that there are (n+1)^(n-1) parking functions with n cars and spaces`):
print(``):
print(`It   accompanies the JMM talk 2019 by Yukun Yao and Doron Zeilberger `):
print(`Jan. 19, 2019, 2:00-2:20pm, Room 321, Baltimore Convention Center`):
print(``):
print(`Please report bugs to DoronZeil at gmail dot com `):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://sites.math.rutgers.edu/~zeilberg/  .`):

print(`---------------------------------------`):
 print(`For a list of the Supporting procedures type ezra1();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

print(`---------------------------------------`):
 print(`For a list of the MAIN procedures type ezra();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`---------------------------------------`):

with(combinat):

ezra1:=proc()

if args=NULL then
 print(` The supporting procedures are: CPark1, Park1 `):
 print(``):

else
ezra(args):
fi:

end:

ezra:=proc()

if args=NULL then
 print(`The main procedures are: AllParking, CPark, Empty, EmptyMates, EmptyMatesV, Park, PF(n) `):
 print(` `):


elif nops([args])=1 and op(1,[args])=AllParking then
print(`AllParking(n): all the parking arrangements (possibly with circular) for n cars`):

elif nops([args])=1 and op(1,[args])=CPark then
print(`CPark(P): Like Park(P) (q.v.) but in  a circular street with an additional parking spot, n+1. Try:`):
print(`CPark([1,2,2,3]);`):

elif nops([args])=1 and op(1,[args])=CPark1 then
print(`CPark1(Cu,c,i): Like Park1(Cu,c,i) but with an additional parking space , n+1, and in a circular street. Try:`):
print(`CPark1([2,1,0,0],3,4);`):

elif nops([args])=1 and op(1,[args])=Empty then
print(`Empty(P): the empty space in a circular street with preferance function P, where P has length n and its componets are in [1,n+1]. Try: `):
print(`Empty([3,3,3]); `):

elif nops([args])=1 and op(1,[args])=EmptyMates then
print(`EmptyMates(P): illustrates Pollak's trivial but crucial lemma. Try: `):
print(`EmptyMates([3,3,3]); `):

elif nops([args])=1 and op(1,[args])=EmptyMatesV then
print(`EmptyMatesV(P): Verbose version of EmptyMates(P). Try: `):
print(`EmptyMatesV([3,3,3]); `):

elif nops([args])=1 and op(1,[args])=Park then
print(`Park(P): inputs a list preferance vector P where P[i] is car i-th peferred space, outputs the final arrangement, or FAIL. Try`):
print(`Park([1,2,2,3]);`):

elif nops([args])=1 and op(1,[args])=Park1 then
print(`Park1(Cu,c,i): inputs a list Cu (where 0 denotes empty space) where the current cars are placed, and`):
print(`someone, called c, with preferance i, outputs FAIL or the new situations where to place c. Try:`):
print(`Park1([2,1,0,0],3,4);`):

elif nops([args])=1 and op(1,[args])=PF(n) then
print(`The set of parking functions with n cars. Try:`):
print(`PF(4); `):



else
print(`There is no ezra for`,args):
fi:
 
end:






ez:=proc(): print(`, Empty(P) , EmptyMates(P), EmptyMatesV(P), AllParking(n)  `): end:

#Park1(Cu,c,i): inputs a list Cu (where 0 denotes empty space) where the current cars are placed, and
#someone, called c, with preferance i, outputs FAIL or the new situations where to place c. Try:
#Park1([2,0,1],3,1);
Park1:=proc(Cu,c,i) local j:

for j from i to nops(Cu) while Cu[j]<>0 do od:
if j=nops(Cu)+1 then
 RETURN(FAIL):
else
 RETURN([op(1..j-1,Cu),c,op(j+1..nops(Cu),Cu)]):
fi:
end:


#Park(P): inputs a list in [n]^n and outputs the final parking assignment
Park:=proc(P) local gu,n,i:

if not (type(P,list) and {op(P)} minus {seq(i,i=1..nops(P))}={}) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

n:=nops(P):
gu:=[0$n]:

for i from 1 to n do
gu:=Park1(gu,i,P[i]):
 if gu=FAIL then
   RETURN(FAIL):
 fi:
od:
gu:

end:

#AllF1(n,k): all the lists of length k with entries in {1,...,n}. Try:
#AllF1(3,2);
AllF1:=proc(n,k) local gu,gu1,i:
option remember:
if k=0 then
 RETURN({[]}):
fi:
gu:=AllF1(n,k-1):

{seq(seq([op(gu1),i],gu1 in gu),i=1..n)}:

end:


#PF(n): all the parking functions, together with their final succesful spots
PF:=proc(n) local gu,mu,mu1,lu:
mu:=AllF1(n,n):

gu:={}:

for mu1 in mu do
 lu:=Park(mu1):
  if lu<>FAIL then
   gu:=gu union {mu1}:
  fi:
od:

gu:
end:



#CPark1(Cu,c,i): inputs a list Cu (where 0 denotes empty space) where the current cars are placed, and
#someone, called c, with preferance i, finds the new locations with a circular street. Try:
#CPark1([2,0,1,0],3,3);
CPark1:=proc(Cu,c,i) local j,n:
n:=nops(Cu)-1:
for j from i to n+1 while Cu[j]<>0 do od:
if  j<=n+1 then
 RETURN([op(1..j-1,Cu),c,op(j+1..nops(Cu),Cu)]):
else
 for j from 1 to n while Cu[j]<>0 do od:
 RETURN([op(1..j-1,Cu),c,op(j+1..nops(Cu),Cu)]):
fi:
end:

#CPark(P): inputs a list in [n+1]^n and outputs the final parking assignment in a circular street. Try
#CPark([3,3,3]);
CPark:=proc(P) local gu,n,i:

if not (type(P,list) and {op(P)} minus {seq(i,i=1..nops(P)+1)}={}) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

n:=nops(P):
gu:=[0$(n+1)]:

for i from 1 to n do
 gu:=CPark1(gu,i,P[i]):
od:
gu:

end:



#Empty(P): inputs a preferance function P, and outputs its empty spot
Empty:=proc(P) local gu,i:
gu:=CPark(P):
for i from 1 to nops(gu) while gu[i]<>0 do od:
i:
end:

#EmptyMates(P): inputs  a preferance function and outputs all its circular mates and their empties. Try:
#EmptyMates([3,3,3]);
EmptyMates:=proc(P) local i,gu,i1,P1,n:
n:=nops(P):
P1:=P:

gu:=[[P1,Empty(P1)]]:

for i from 1 to n do
 P1:=[seq((P1[i1] mod (n+1))+1,i1=1..nops(P))]:
 gu:=[op(gu),[P1,Empty(P1)]]:
od:
gu:

end:


#AllParking(n): all the parking arrangements (possibly with circular) for n cars
AllParking:=proc(n) local gu,gu1,lu:
gu:=AllF1(n,n):

for gu1 in gu do
 lu:=Park(gu1):
 if lu<>FAIL then
  print(`For the preferance vector`, gu1, `it is possible to park everyeone and they wind up as:`,lu):
else
  lu:=CPark(gu1):
  print(`For the preferance vector`, gu1, `it is not possible to park everyeone, but with a circular street it winds up like this:`, lu):
fi:
od:

end:


#EmptyMatesV(P): inputs  a preferance function and outputs all its circular mates and their empties. Try:
#EmptyMatesV([3,3,3]);
EmptyMatesV:=proc(P) local i,gu,i1,P1,n:
n:=nops(P):
P1:=P:

print(`If the preferance function is`, P1, `then the final parking arrangement is`, CPark(P1), `whose empty is`, Empty(P1)):

gu:=[[P1,Empty(P1)]]:

for i from 1 to n do
 P1:=[seq((P1[i1] mod (n+1))+1,i1=1..nops(P))]:
print(`Moving`, i , ` units clockwise we get`, P1, `with final parking arrangement is`, CPark(P1), `whose empty is`, Empty(P1) ):
  gu:=[op(gu),[P1,Empty(P1)]]:
od:
gu:

end: