Help:=proc()
print(`randB(n,m,k,x), Ev(f,n,x,v), randT(n,m,k,x)`):
print(`EvT(T,n,x,v), Cycle(T,x,n,v)`):
print(`MaxCyc(n,m,k,K)`):
end:

#randB(n,m,k,x):a random Boolean function in disjunctive
#normal form ("sum" of "products"} of Boolean literals
#in the variables x[1], ..., x[n]
#n=number of variables 
#m is the number of clauses
#k is the number of terms in each clause
#with the data structre
#{{x[1],1-x[3],x[4]},{ x[2],1-x[3],x[5]}}
randB:=proc(n,m,k,x) local f,ra1,ra2,i,j,david,g:
f:={}:

ra1:=rand(1..n):

ra2:=rand(0..1):

for i from 1 to m do
g:={}:
 for j from 1 to k do
   david:=ra1():
   if not member(x[david],g) and not member(1-x[david],g)
      then
          
       if ra2()=1 then
          g:=g union {x[david]}:
        else
          g:=g union {1-x[david]}:
       fi:
   fi:
  od:

f:=f union {g}:

od:

f:
end:


#Ev(f,n,x,v): evaluates a Boolean function f
#in x[1], ..., x[n] with the above data structre
#at the point x[1]=v[1], ..., x[n]=v[n]
Ev:=proc(f,n,x,v) local g,i:
max(seq(min(subs({seq(x[i]=v[i],i=1..n)}, g)), g in f)):

end:


#randT(n,m,k,x): a random Boolean transformation
randT:=proc(n,m,k,x) local i:

[seq(randB(n,m,k,x),i=1..n)]:

end:


 #EvT(T,n,x,v): evaluates a Boolean transformation
#in x[1], ..., x[n] with the above data structre
#at the point x[1]=v[1], ..., x[n]=v[n]
EvT:=proc(T,n,x,v) local i:

[seq(Ev(T[i],n,x,v),i=1..n)]:
end:

#The first cycle encountered in the orbit of
#the transformation T starting at v
Cycle:=proc(T,x,n,v) local aron,chris,i:
aron:=[v]:

while nops(aron)=nops(convert(aron,set)) do
 aron:=[op(aron), EvT(T,n,x,aron[nops(aron)])]:
od:

chris:=aron[nops(aron)]:

for i from 1 to nops(aron) while aron[i]<>chris do od:

[op(i..nops(aron),aron)]:
end:

#MaxCyc(n,m,k,K): finds the largest length of
#orbits of Boolean transformations applied to random
#starting points in {0,1/2,1}^n K times
MaxCyc:=proc(n,m,k,K) local rec, cha,v,i,ra,T,x,hope,i1:
rec:=1:
cha:=0:
ra:=rand(0..2):

for i from 1 to K do

 T:=randT(n,m,k,x):
v:=[seq(ra()/2,i1=1..n)]:
hope:=nops(Cycle(T,x,n,v))-1:
 if hope>rec then
  rec:=hope:
  cha:=[v,T]:
 fi:
od:

rec,cha:

end: