#OK to post homework
#George Spahn, 1/31/2021, Assignment 2

#SetToVec(S,n) INPUT a subset S of {1,...,n}. OUTPUT 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 g:

if not (type(S,set) and type(n,integer)) then
 RETURN(FAIL):
fi:

if n<0 then
print(n, `should be non-negative `):
 RETURN(FAIL):
fi:

if false in {seq(type(s,integer) and s > 0 and s <=n ,s in S)} then
print(`set is not a subset of  {1,...,n}`):
 RETURN(FAIL):
fi:

g:=proc(T,i):
if i in T then
 RETURN(1):
fi:
0
end:

[seq(g(S,i),i=1..n)]:
end:


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

VecToSet:= proc(v) local n,g:
n:=nops(v):

g:=proc(b,x):
if b > 0 then
 RETURN(x):
fi:
0
end:

{ seq(g(v[i],i), i=1..n) } minus {0}:
end:


#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 ps,bo,s,v: 

ps := MyPS({seq(i,i=1..n)}):
for s in ps do
 if not(VecToSet(SetToVec(s,n))=s)  then
  print(s, VecToSet(SetToVec(s,n))):
  RETURN(FAIL):
 fi:
od:
print(`so far so good`):
bo := Box([1$n]):
for v in bo do
 if not(SetToVec(VecToSet(v),n)=v)  then
  print(v, SetToVec(VecToSet(v),n)):
  RETURN(FAIL):
 fi:
od:
print(`all good`):
end:


#NextInLine(L,v) Inputs a list L of nonnegative integers and a member v of the
# list of lists (dictionary) and returns the vector right after it 
# (in dictionary (lex.) order) 
# without actually constructiong the (usually) very large set Box(L)

NextInLine:= proc(L,v) local n,v1:

n:=nops(v):

if n=0 then
 print(`You have reached the top`):
 RETURN(FAIL):
fi:

v1:=[op(1..n-1,v)]:
if not(v[n]=L[n]) then
 RETURN([op(v1),v[n]+1]):
fi:

v1:=NextInLine(L,v1):

if v1=FAIL then
 RETURN(FAIL):
else
RETURN([op(v1),0]):
fi:

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,j:
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: