# OK to post homework
# Alex Varjabedian, 18-Apr-2024, Homework 25

Help := proc() print(`VerifyOpt1(n,G,B1,B2)\nZKP1v2(n,G,pi,Opt)\nZKP(n,G,pi,K)`) end:

with(combinat):

LD:=proc(p) local i:i:=rand(1..denom(p))(): if i<=numer(p) then true:else false:fi:end:

RG:=proc(n,p) local i,j,G:
G:={}:
for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
G:  
end:

RHG:=proc(n,p) local i,j,G,pi:
pi:=randperm(n):
G:={seq({pi[i],pi[i+1]},i=1..n-1), {pi[n],pi[1]}}:
for i from 1 to n do
 for j from i+1 to n do
  if LD(p) then
    G:=G union {{i,j}}:
  fi:
 od:
od:
[G, pi]:  
end:

ZKP1:=proc(n,G,pi,Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:
for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:
if Opt=1 then
 [op(B1),op(B2)]:
else
 {seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]}:
fi:
end:

######################################################
# -------------------------------------------------- #
# PART 2 - VerifyOpt1(n,G,B1,B2), ZKP1v2(n,G,pi,Opt) #
# -------------------------------------------------- #
######################################################

VerifyOpt1 := proc(n, G, B1, B2) local u, v: evalb(G = {seq(seq(`if`(B2[{u, v}] = 1, {u, v}, NULL), v in op(B1)), u in op(B1))} minus {NULL}) end:

ZKP1v2 := proc(n, G, pi, Opt) local B1,B2,i,j,sig:
sig:=randperm(n):
for i from 1 to n do
 B1[i]:=sig[i]:
od:
for i from 1 to n do
 for j from i+1 to n do
   if member ({i,j},G) then
     B2[{sig[i],sig[j]}]:=1:
   else
    B2[{sig[i],sig[j]}]:=0:
   fi:
od:
od:
if Opt=1 then
 VerifyOpt1(n, G, B1, B2):
else
 evalb({seq(B2[{sig[pi[i]],sig[pi[i+1]]}],i=1..n-1),B2[{sig[pi[n]],sig[pi[1]]}]} = {1}):
fi:
end:

##########################
# ---------------------- #
# PART 3 - ZKP(n,G,pi,K) #
# ---------------------- #
##########################

ZKP := proc(n, G, pi, K) local r, i:
r := rand(1..2):
for i from 1 to K do
 if ZKP1v2(n, G, pi, r()) = false then return false fi:
od:
true:
end: