#OK to post homework
#Victoria Chayes, 1/31/2021, Assignment 2

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

#############################################


#2 Write a procedure SetToVec(S,n) that 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 v,i:
if S={} then
  return([0$n]):
fi:

if not (type(S, set) and {seq(type(s,integer),s in S)}={true} and min(S)>0 and max(S)<=n) then
  return(FAIL):
fi:
v:=[]:
for i from 1 to n do
  if i in S then
    v:=[op(v),1]:
  else
    v:=[op(v),0]:
  fi:
od:
v:
end:



#3  Write a procedure VecToSet(v) that inputs a 0-1 vector v 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,i,n:
if not (type(v, list) and {seq(type(v[i],integer),i=1..nops(v))}={true} and min(v)>=0 and max(v)<=1) then
  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:
S:
end:



#4 Write a procedure CheckBij(n) that 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 B,P,i:
B:=Box([1$n]):
for i from 1 to nops(B) do
if not B[i]=SetToVec(VecToSet(B[i]),n) then
  print(B[i]):
  print(`Box check failed.`):
  return(FAIL):	
fi:
od:

print(`Box check has concluded`):

P:=MyPS({seq(i,i=1..n)}) minus {}:   #the procedure SetToVec
for i from 1 to nops(P) do
if not P[i]=VecToSet(SetToVec(P[i],n)) then
  print(P[i]):
  print(`Power Set check failed.`):
  return(FAIL):	
fi:
od:

print(`Power set check has concluded`):
end:



#5 Write a procedure 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,n:
if not (type(L,list) and type(v,list)) then  #initial condition checking
  print(`bad input: must both be lists`):
  return(FAIL):
fi:

n:=nops(L):
if not (n>0 and nops(v)=n) then  #initial condition checking
  print(`bad input: vector incorrect length`):
  return(FAIL):
fi:

if v=L then  #initial condition checking
  print(`you are at the end of your dictionary`):
  return(FAIL):
fi:

i:=1:
while i<=n do
  if v[-i]<L[-i] then 
    return([op(v[1..n-i]),v[-i]+1,0$(i-1)]):
  elif v[-i]>L[-i] then
    print(`bad input: not in dictionary`):
    return(FAIL):
  else
    i:=i+1:
  fi:
od:
end:

#To test this procedure, we compare its output to doing it the naive long way:

#DumbNextInLine(L,v):
#INPUTS: 
#  a list L
#  a vector v, which would belong to Box(L) 
#OUTPUTS:
#  the vector after v in Box(L)
DumbNextInLine:=proc(L,v) local B, i:
B:=Box(L):
i:=1:
while B[i]<>v do
  i:=i+1:
od:
B[i+1]:
end:

#DumbNextInLine and NextInLine output the same results upon testing with smaller lists, so I am happy.

################
# FROM C2.TXT  #
################


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:=proc(L) local k,i,L1,B1,b1:
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: