#OK to post homework
#Wanying Rao, 01/27/2021, Assignment 2

Help := proc(): print(`SetToVec(S,n), VecToSet(v), CheckBij(n), NextInLine(L,v)`): end:
with(combinat):
with(linalg):

#2
#SetToVec(S,n): Inputs a subset S of {0,...,n} and outputs the 0-1 vector of length n
#such that v[i]=1 iff i belongs to S.

SetToVec := proc(S,n) local v,i:

if not type(S,set) then
print(S, `should be a set `):
 RETURN(FAIL):
fi:

if not (type(n,integer) and n >= 0) then
print(n, `should be a non-negative integer`):
 RETURN(FAIL):
fi:

if not S subset {seq(j,j=1..n)} then
print(S, `should be a subset of {1,...,n}`):
RETURN(FAIL):
fi:

v := vector(n,0):
for i from 1 to n do
 if i in S then v[i] := 1: fi:
od:

RETURN(op(v)):
end:


#3
#VecToSet(v): Inputs a 0-1 vector and outputs the subset of {1,...,n}(where n=nops(v))
#such that v[i]=1 iff i belongs to S

VecToSet := proc(v) local S,n,i,j:

if not type(v, vector) then
print(v, `should be a vector`):
 RETURN(FAIL):
fi:

if not convert(v, set) subset {0,1} then
print(v, `should be a 0-1 vector`):
 RETURN(FAIL):
fi:

n := nops(v):
S :={}:

for i from 1 to n do
 if v[i] = 1 then S := S union {i}: fi:
od:
RETURN(S):
end:

#4
CheckBij := proc(n) local v,S:

if not (type(n,integer) and n > 0) then
print(n, `should be a positive integer`):
 RETURN(FAIL):
fi:

for v in Box([1$n]) do
 if not convert(SetToVec(VecToSet(convert(v, vector)),n),list)=v then
  RETURN(FAIL):
 fi:
od:

for S in MyPS({seq(i,i=1..n)}) do
 if not VecToSet(SetToVec(S,n))=S then
  RETURN(FAIL):
 fi:
od:

RETURN(Correct):
end:

#5
#NextInLine(L,v): Inputs a list L and a member v from Box(L) and outputs the list right #after it (in dictionary order)

NextInLine := proc(L,v) local u,n,i:

if v = L then
print(v, `is the last one`):
 RETURN(FAIL):
fi:

n := nops(L):
u := v:
u[n] := u[n]+1:
for i from 0 to n-1 do
 if u[n-i] = L[n-i]+1 then 
  u[n-i] := 0:
  u[n-i-1] := u[n-i-1]+1:
 fi:
od:
RETURN(u):
end:






#####C2#####
#C2.txt: Maple code for Lecture 2 of Experimaental Mathematics (Rutgers Univ. Spring 2021) by Dr. Z.
Help2:=proc(): print(` FP(pi) , MomFP(n,k), MyPS(S), Box(L)  `):
end:

with(combinat):

#FP(pi): Inputs a permutation pi of {1,...n}, (where n=nops(pi)) and outputs an integer
#between 0 and n indicating the number of fixed points, i.e. the number of places i such that
#pi[i]=i. Note that if pi is a derangement, then FP(pi)=0.
FP:=proc(pi) local n,i,f:

n:=nops(pi):
f:=0:

for i from 1 to n do
 if pi[i]=i then
  f:=f+1:
 fi:
od:
f:

end:




#MomFP(n,k): Inputs a positive integer n and outputs the EXACT (not approximate)
#value of the average of the k-th power of FP(pi) over all permutations
MomFP:=proc(n,k) local S,pi:S:=permute(n):add(FP(pi)^k, pi in S)/nops(S):end:

#MyPS(S): Inputs a set S and outputs the powerset of S, i.e. the set of all
#subsets  of S
MyPS:=proc(S) local s,S1,PS1,s1:

if not type(S,set) then
print(S, `should be a set `):
 RETURN(FAIL):
fi:

if S={} then
 RETURN({{}}):
fi:

s:=S[nops(S)]:

S1:=S minus {s}:

PS1:=MyPS(S1):

PS1 union { seq( s1 union {s}, s1 in PS1)}:

end:

#Box(L): Inputs a list L (where k=nops(L)) of non-negative integers L outputs
#the  LIST of all LISTS [a1,a2,..., ak] in LEX ORDER such that ai is in {0,1,.., L[i])
#In particular the n-dim UNIT cube would be Box([1$n]);
Box:=proc(L) local k,i,L1,B1,b1:
option remember:

if not type(L,list) then
  print(L, `should be a list `):
 RETURN(FAIL):
fi:

k:=nops(L):
if k=0 then 
 RETURN([[]]):
fi:
 if not ({seq(type(L[i],integer),i=1..nops(L))}={true} and min(op(L))>=0) then
   print(`bad input`):
  RETURN(FAIL):
 fi:




L1:=[op(1..k-1,L)]:

B1:=Box(L1):
 [ seq(seq([op(B1[j]),i],i=0..L[k]),j=1.. nops(B1))]:
end:



 





###From C1.txt
#C1.txt: Maple Code for ExpMath Spring 2021

Help1:=proc(): print(` LC(p) , IsDer(pi), RandPer(n) `): end:

#LC(p): Inputs a RATIONAL number p and outputs a pseudo-random number
#1 with probability p and 2 with probability 1-p
LC:=proc(p) local m,n,r:

if not ( type(p,numeric) and p>=0  and p<=1) then
 RETURN(FAIL):
fi:

if p=0 then
 RETURN(2):
fi:

if p=1 then
 RETURN(1):
fi:

if not type(p,fraction) then
 RETURN(FAIL):
fi:

m:=numer(p):
n:=denom(p):
r:=rand(1..n)():

if r<=m then
  1:
else
 2:
fi:

end:


#DEF: A derangement of {1, ...,n} is a permutation such that pi[i]<>i for every i
#IsDer(pi): inputs a permutation of {1,...,n} pi (n=nops(pi))
#and outputs true iff it is a derangement
IsDer:=proc(pi) local n,i:
n:=nops(pi):
for i from 1 to n do
 if pi[i]=i then
    RETURN(false):
 fi:
od:
true:
end:

#RandDer(n): Generates a random derangement using the NAIVE approach suggested by
#Alon Itai in his not entirely-raving Math review of the Nijenhuius-Wilf classic
RandDer:=proc(n) local pi:

pi:=randperm(n):

while  not IsDer(pi) do
pi:=randperm(pi):
od:
pi:
end:
#END C1.txt