#OK to post homework
#Blair Seidler, 2021-01-31, Assignment 2

with(combinat):

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

# 2.

#SetToVec(S,n)
# inputs a subset S of {1,...,n} and outputs the 0-1 vector of length n such that v[i]=1 iff
#i belongs to S. Be sure to check that the input is legal (i.e. that S is indeed a set, and
#that n is a non-neg. integer and that S is indeed a subset of {1,...,n}.
SetToVec:=proc(S,n) local i,k:

if not type(S,set)  then
 print(`S must be a set`):
 RETURN(FAIL):
fi:
if not (type(n,integer) and n>=0) then
 print(`n must be non-negative integer`):
 RETURN(FAIL):
fi:
if n=0 then
 RETURN([]):
fi:
k:=nops(S):
if k>0 and not {seq(type(S[i],integer) and S[i]>0 and S[i]<=n,i=1..k)}={true} then
 print(`S must be a subset of {1,...,n}`):
 RETURN(FAIL):
fi:

[seq(eval(member(i,S),[true=1,false=0]),i=1..n)]:

end:

# 3.

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

if not type(v,list)  then
 print(`v must be a vector`):
 RETURN(FAIL):
fi:
n:=nops(v):
if n=0 then
 RETURN({}):
fi:
if not {seq(type(v[i],integer) and (v[i]=0 or v[i]=1),i=1..n)}={true} then
 print(`v must be a vector over {0,1}`):
 RETURN(FAIL):
fi:

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

end:

# 4.

#CheckBij(n) checks that SetToVec(VecToSet(v),n)=v is always true for each member of
#Box([1$n]) and VecToSet(SetToVec(S,n))=S for each member of MyPS({seq(i,i=1..n)}).
CheckBij:=proc(n) local S,B,s,v:
if not (type(n,integer) and n>=0) then
 print(`n must be a nonnegative integer`):
 RETURN(FAIL):
fi:
S:=MyPS({seq(i,i=1..n)}):

for s in S do
 if not (VecToSet(SetToVec(s,n))=s) then
  print(`failed on `,s):
  RETURN(false):
 fi:
od:

B:=Box([1$n]):
for v in B do
 if not (SetToVec(VecToSet(v),n)=v) then
  print(`failed on `,v):
  RETURN(false):
 fi:
od:

true:

end:

# 5.
#NextInLine(L,v) that inputs a list L and a member v of the list of lists (dictionary) and
#returns the vector right after it (in dictionary (lex.) order) without actually constructing
#the (usually) very large set Box(L)
NextInLine:=proc(L,v) local i,k,pos,nv:
if not type(v,list)  then
 print(`v must be a vector`):
 RETURN(FAIL):
fi:
k:=nops(L):

if k=0 then
 RETURN(NoNextVector):
fi:

if not ({seq(type(L[i],integer),i=1..k)}={true} and min(op(L))>=0) then
 print(`L must be list of non-negative integers`):
 RETURN(FAIL):
fi:
if not (nops(v)=k) then
 print(`v has incorrect length`):
 RETURN(FAIL):
fi:
if not ({seq(type(v[i],integer),i=1..k)}={true}
		and {seq(convert(v[i]<=L[i],truefalse),i=1..k)}={true}
		and min(op(v))>=0) then
 print(`entry of v out of range`):
 RETURN(FAIL):
fi:

#Find the last position which is not at its maximum value
pos:=0:
for i from 0 to k-1 do
  if v[k-i]<L[k-i] then
    pos:=k-i:
    break:
  fi:
od:

#All positions at maximum value
if pos=0 then
 RETURN(NoNextVector):
fi:

#Increment last position not at max, zero all subsequent positions
nv:=v:
nv[pos]:=nv[pos]+1:
for i from pos+1 to k do
  nv[i]:=0:
od:

nv:

end:

#-------------------------------------------------
#The following procedures are included from C2.txt
#-------------------------------------------------

#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(`bad input`):
 RETURN(FAIL):
fi:

k:=nops(L):

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

if not ({seq(type(L[i],integer),i=1..k)}={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: