######################################################################
#SLprog.txt Save this file as SLprog.txt                             #
#To use it, stay in the                                              #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read SLprog.txt : <Enter>                          #
##Then follow the instructions given there                           #
##                                                                   #
##Written by Blair Seidler, Rutgers University ,                     #
#blair at math dot rutgers dot edu                                   #
######################################################################
 
#Created: Sep. 2021
 
print(`Created: Sep. 2021`):
print(`This is SLprog `):
print(`to explore straight-line programs`):
print(``):
print(`In this package, we will represent a straight-line program as `):
print(`a list of lists, such as [[1],[2],[AND,1,2]].`):
print(`The sample program expects a vector x of length 2`):
print(`as input, and will return x[1] and x[2] as output.`):
print(``):
print(`The SLP versions of functions use NOT, AND, OR as`):
print(`the possible gate types.`):
print(`The SLPn versions use NOT and the integers 1..10 as`):
print(`the possible gate types. See HelpSL(functions).`):
print(``):
print(`In this package, we will represent a Boolean function as `):
print(`a set of vectors (lists) in {-1,0,1}^n, where -1 is false, `):
print(`1 is true, and 0 is don't care.`):
print(`{[-1,0,1]} can be interpreted as "not x[1] and x[3]"`):
print(`{[-1,0,0],[0,0,1]} can be interpreted as "not x[1] or x[3]"`):
print(``):
print(`written by Blair Seidler.`):
print(``):
print(`Please report bugs to blair at math dot rutgers dot edu`):
print(``):
print(`For a list of the procedures type HelpSL();, for help with`):
print(`a specific procedure, type HelpSL(procedure_name);   .`):
print(``):
print(`For a list of the ten Boolean functions used as gates in`):
print(`the SLPn procedures, type HelpSL(functions); .`):

with(combinat):

HelpSL:=proc():

if args=NULL then
print(`The main procedures are: `):
print(`EvalSLP,SLPtoBool,BoolToSLP`):
print(`EvalSLPn,SLPntoBool,RandSLPn`):


elif nops([args])=1 and op(1,[args])=EvalSLP then
print(`EvalSLP(p,v [,psa]): inputs a straight-line program p (AND/OR/NOT)`):
print(`and a vector v in {-1,0,1}^n. Outputs the result`):
print(`of the SLP on that input.`):
print(``):
print(`If the third argument is true, any satisfying assignments`):
print(`will be printed. This is useful for evaluating vectors`):
print(`containing 0's when you want to know the possible variable`):
print(`assignments for which the SLP returns 1. Default is false.`):
print(``):
print(`For example, EvalSLP([[1],[2],[AND,1,2]],[1,1]); will output 1.`):
print(``):
print(`EvalSLP([[1], [2], [OR, 1, 2]], [0, 1]); will output 1.`):
print(``):
print(`EvalSLP([[1], [2], [OR, 1, 2]], [0, 1], true); will print`):
print(`Satisfying assignment: , [-1, 1]`):
print(`Satisfying assignment: , [ 1, 1]`):
print(`and return 1.`):

elif nops([args])=1 and op(1,[args])=EvalSLPn then
print(`EvalSLPn(p,v [,psa]): inputs a straight-line program p (numeric gates)`):
print(`and a vector v in {-1,0,1}^n. Outputs the result`):
print(`of the SLP on that input.`):
print(``):
print(`If the third argument is true, any satisfying assignments`):
print(`will be printed. This is useful for evaluating vectors`):
print(`containing 0's when you want to know the possible variable`):
print(`assignments for which the SLP returns 1. Default is false.`):
print(``):
print(`For example, EvalSLPn([[1],[2],[1,1,2]],[1,1]); will output 1.`):
print(``):
print(`EvalSLPn([[1], [2], [5, 1, 2]], [0, 1]); will output 1.`):
print(``):
print(`EvalSLPn([[1], [2], [5, 1, 2]], [0, 1], true); will print`):
print(`Satisfying assignment: , [-1, 1]`):
print(`Satisfying assignment: , [ 1, 1]`):
print(`and return 1.`):

elif nops([args])=1 and op(1,[args])=SLPtoBool then
print(`SLPtoBool(p): inputs a straight-line program p (AND/OR/NOT)`):
print(`and outputs the set of vectors in {-1,1}^n`):
print(`on which the program resturns 1.`):
print(`For example, SLPtoBool([[1],[2],[AND,1,2]]); will output {[1,1]}.`):

elif nops([args])=1 and op(1,[args])=SLPntoBool then
print(`SLPntoBool(p): inputs a straight-line program p (numeric gates)`):
print(`and outputs the set of vectors in {-1,1}^n`):
print(`on which the program resturns 1.`):
print(`For example, SLPntoBool([[1],[2],[1,1,2]]); will output {[1,1]}.`):

elif nops([args])=1 and op(1,[args])=BoolToSLP then
print(`BoolToSLP(f): inputs a Boolean function f`):
print(`as a set of vectors in {-1,0,1}^n and returns`):
print(`a straight-line program p.`):
print(`For example, BoolToSLP([[1, 0, -1], [-1, 1, 1]]); will output`):
print(`[[1], [2], [3], [NOT, 3], [AND, 1, 4], [NOT, 1],`):
print(` [AND, 6, 2], [AND, 3, 7], [OR, 5, 8]]`):

elif nops([args])=1 and op(1,[args])=RandSLPn then
print(`RandSLPn(n,g): inputs a number of variables n`):
print(`and a number of gates g. Outputs a randomly`):
print(`generated SLP with n variables and g gates,`):
print(`where the gates are selected from the ten`):
print(`distinct functions which depend on both of`):
print(`their input variables.`):
print():
print(`For example, RandSLPn(3,2) may output`):
print(`[[1], [2], [3], [5, 1, 3], [9, 2, 4]]`):
elif nops([args])=1 and op(1,[args])=functions then
print(`Possible gate types for SLPn functions, where`):
print(`i is the number of an input variable 1..n`):
print(`and A,B are outputs of previous lines including`):
print(`the input variables 1..n`):
print():
print(`[TRUE]: Always returns 1`):
print(`[FALSE]: Always returns -1`):
print(`[i] on line i: Loads input from input vector`):
print(`[i] after line i: Returns value of input i`):
print(`[NOT,A]: negates A`):
print(`[1,A,B]: returns A and B`):
print(`[2,A,B]: returns A and not B`):
print(`[3,A,B]: returns not A and B`):
print(`[4,A,B]: returns A xor B`):
print(`[5,A,B]: returns A or B`):
print(`[6,A,B]: returns not A and not B`):
print(`[7,A,B]: returns A equiv B`):
print(`[8,A,B]: returns B implies A`):
print(`[9,A,B]: returns A implies B`):
print(`[10,A,B]: returns not(A and B)`):
else
print(`There is no Help for`,args):
fi:
 
end:

BoolToSLP:=proc(f) local i,n,c,m,m2,m3,numv,cur,prev,T,P,clauses:
if nops(f)=0 then
  print(`Function is empty`):
  RETURN(FAIL):
fi:
prev:=0:
n:=nops(f[1]):
P:=[seq([i],i=1..n)]:
T:=table([seq([i]=i,i=1..n)]):
cur:=n+1:
clauses:={}:
for c in f do
  numv:=add(abs(c[i]),i=1..n):
  if numv=1 then
    i:=add(i*c[i],i=1..n):
    if i>0 then
      clauses:=clauses union {i}:
    else
      i:=-1*i:
      if type(T[[NOT,i]],integer) then
        clauses:=clauses union {T[[NOT,i]]}:
      else
        P:=[op(P),[NOT,i]]:
        T[[NOT,i]]:=cur:
        clauses:=clauses union {cur}:
        cur:=cur+1:
      fi:
    fi:
  else
    for i from 1 to n do
      if c[i]<>0 then m:=i: break: fi:
    od:
    for i from m+1 to n do
      if c[i]<>0 then
        m2:=i:
        m3:=i+1:
        if c[m]=-1 then
          if type(T[[NOT,m]],integer) then
            m:=T[[NOT,m]]:
          else
            P:=[op(P),[NOT,m]]:
            T[[NOT,m]]:=cur:
            m:=cur:
            cur:=cur+1:
          fi:
        fi:
        if c[i]=-1 then
          if type(T[[NOT,i]],integer) then
            m2:=T[[NOT,i]]:
          else
            P:=[op(P),[NOT,i]]:
            T[[NOT,i]]:=cur:
            m2:=cur:
            cur:=cur+1:
          fi:
        fi:
        break:
      fi:
    od:

    P:=[op(P),[AND,m,m2]]:
    T[[AND,m,m2]]:=cur:
    cur:=cur+1:
  
    for i from m3 to n do
      if c[i]=1 then
        P:=[op(P),[AND,i,cur-1]]:
        T[[AND,m,m2]]:=cur:
        cur:=cur+1:
      elif c[i]=-1 then
        if type(T[[NOT,i]],integer) then
          P:=[op(P),[AND,T[[NOT,i]],cur-1]]:
          cur:=cur+1:
        else
          P:=[op(P),[NOT,i]]:
          T[[NOT,i]]:=cur:
          P:=[op(P),[AND,cur-1,cur]]:
          cur:=cur+2:
        fi:
      fi:
    od:
  clauses:=clauses union {cur-1}:
  fi:
od:
if nops(clauses)<2 then RETURN(P): fi:
P:=[op(P),[OR,op(1..2,clauses)]]:
cur:=cur+1:
for i from 3 to nops(clauses) do
  P:=[op(P),[OR,clauses[i],cur-1]]:
  cur:=cur+1:
od:
P:
end:

BFand:=proc(a,b):
if not({a,b} subset {-1,0,1}) then RETURN(FAIL): fi:
  if a+b=2 then
    RETURN(1):
  elif a+b=1 then
    RETURN(0):
  elif a+b<0 then
    RETURN(-1):
  else
   RETURN(a*b):
  fi:
end:

BFor:=proc(a,b):
if not({a,b} subset {-1,0,1}) then RETURN(FAIL): fi:
  if a=1 or b=1 then
    RETURN(1):
  elif a+b=-2 then
    RETURN(-1):
  else
   RETURN(0):
  fi:
end:

BFnot:=proc(a):
if not(a in {-1,0,1}) then RETURN(FAIL): fi:
RETURN(-1*a):
end:

BFeval:=proc(f,a,b):
if not({a,b} subset {-1,0,1}) then RETURN(FAIL): fi:
if not(f in {seq(i,i=1..10)}) then RETURN(FAIL): fi:
if f=1 then
  RETURN(min(a,b)):
elif f=2 then
  RETURN(min(a,-b)):
elif f=3 then
  RETURN(min(-a,b)):
elif f=4 then
  RETURN(-(a*b)):
elif f=5 then
  RETURN(max(a,b)):
elif f=6 then
  RETURN(min(-a,-b)):
elif f=7 then
  RETURN(a*b):
elif f=8 then
  RETURN(max(a,-b)):
elif f=9 then
  RETURN(max(-a,b)):
else
  RETURN(-min(a,b)): 
fi:
end:


EvalSLP:=proc() local p,v,psa,i,T:
if nargs=2 then
  p:=args[1]:
  v:=args[2]:
  psa:=false:
elif nargs=3 then
  p:=args[1]:
  v:=args[2]:
  psa:=args[3]:
else
  print(`Usage: EvalSLP(p,v [,printsat])`):
  RETURN(FAIL):
fi:
if nops(p)=0 then
  print(`Program is empty`):
  RETURN(FAIL):
fi:
for i from 1 to nops(v) do
  if v[i]=0 then
    RETURN(BFor(EvalSLP(p,[op(1..i-1,v),-1,op(i+1..nops(v),v)],psa),EvalSLP(p,[op(1..i-1,v),1,op(i+1..nops(v),v)],psa))):
  fi:
od:
T:=table():
for i from 1 to nops(p) do
  if nops(p[i])=1 then
    if p[i][1]=FALSE then
      T[i]:=-1:
    elif p[i][1]=TRUE then
      T[i]:=1:
    elif p[i][1]=i and i<=nops(v) then
      T[i]:=v[i]:
    elif p[i][1]<=nops(v) then
      T[i]:=T[p[i][1]]:
    else
      RETURN(FAIL):
    fi:
  elif nops(p[i])=2 then
    if p[i][1]=`NOT` then
      T[i]:=BFnot(T[p[i][2]]):
    else
      RETURN(FAIL):
    fi:
  elif nops(p[i])=3 then
    if p[i][1]=`AND` then
      T[i]:=BFand(T[p[i][2]],T[p[i][3]]):
    elif p[i][1]=`OR` then
      T[i]:=BFor(T[p[i][2]],T[p[i][3]]):
    else
      RETURN(FAIL):
    fi:
  else
    RETURN(FAIL):
  fi:
od:
if psa and T[nops(p)]=1 then print(`Satisfying assignment: `,v): fi:
T[nops(p)]:
end:

EvalSLPn:=proc() local p,v,psa,i,T:
if nargs=2 then
  p:=args[1]:
  v:=args[2]:
  psa:=false:
elif nargs=3 then
  p:=args[1]:
  v:=args[2]:
  psa:=args[3]:
else
  print(`Usage: EvalSLP(p,v [,printsat])`):
  RETURN(FAIL):
fi:
if nops(p)=0 then
  print(`Program is empty`):
  RETURN(FAIL):
fi:
for i from 1 to nops(v) do
  if v[i]=0 then
    RETURN(BFor(EvalSLPn(p,[op(1..i-1,v),-1,op(i+1..nops(v),v)],psa),EvalSLPn(p,[op(1..i-1,v),1,op(i+1..nops(v),v)],psa))):
  fi:
od:
T:=table():
for i from 1 to nops(p) do
  if nops(p[i])=1 then
    if p[i][1]=FALSE then
      T[i]:=-1:
    elif p[i][1]=TRUE then
      T[i]:=1:
    elif p[i][1]=i and i<=nops(v) then
      T[i]:=v[i]:
    elif p[i][1]<=nops(v) then
      T[i]:=T[p[i][1]]:
    else
      RETURN(FAIL):
    fi:
  elif nops(p[i])=2 then
    if p[i][1]=`NOT` then
      T[i]:=BFnot(T[p[i][2]]):
    else
      RETURN(FAIL):
    fi:
  elif nops(p[i])=3 then
    T[i]:=BFeval(p[i][1],T[p[i][2]],T[p[i][3]]):
  else
    RETURN(FAIL):
  fi:
od:
if psa and T[nops(p)]=1 then print(`Satisfying assignment: `,v): fi:
T[nops(p)]:
end:


SLPtoBool:=proc(p) local f,i,n,v:
if nops(p)=0 then
  print(`Program is empty`):
  RETURN(FAIL):
fi:
n:=0:
for i from 1 to nops(p) do
  if nops(p[i])=1 then
    if p[i][1]=i then
      n:=i:
    fi:
  else
    break:
  fi:
od:
if n=0 then RETURN(FAIL): fi:
f:={}:
for i from 0 to 2^n-1 do
  v:=IntegerToVec(i,n):
  if EvalSLP(p,v)=1 then
    f:=f union {v}:
  fi:
od:
f:
end:

SLPntoBool:=proc(p) local f,i,n,v:
if nops(p)=0 then
  print(`Program is empty`):
  RETURN(FAIL):
fi:
n:=0:
for i from 1 to nops(p) do
  if nops(p[i])=1 then
    if p[i][1]=i then
      n:=i:
    fi:
  else
    break:
  fi:
od:
if n=0 then RETURN(FAIL): fi:
f:={}:
for i from 0 to 2^n-1 do
  v:=IntegerToVec(i,n):
  if EvalSLPn(p,v)=1 then
    f:=f union {v}:
  fi:
od:
f:
end:

RandSLPng:=proc(n,lo,hi) local g,i,rvs,rff,slp:
g:=hi-lo+1:
if g<1 then print('blorf'): RETURN(FAIL): fi:
rff:=rand(1..10):
if g=1 then
  rvs:=randcomb(n,2):
  RETURN([[rff(),op(rvs)]]):
fi:
rvs:=rand(floor(g/2)):
i:=max(rvs(),rvs()): # To favor more even distributions on left and right sides of last gate
if i=0 then
  slp:=[op(RandSLPng(n,lo,hi-1)),[rff(),rand(1..n)(),hi-1]]:
else
  slp:=[op(RandSLPng(n,lo,lo+i)),op(RandSLPng(n,lo+i+1,hi-1)),[rff(),lo+i,hi-1]]:
fi:
end:

#RandSLPn - generates a random SLP with n variables and g and/or gates
RandSLPn:=proc(n,g) local slp,i:
if n<1 or g<0 then RETURN(FAIL): fi:
slp:=[seq([i],i=1..n)]:
if g=0 then
  i:=rand(-1..2*n)():
  if i=-1 then
    RETURN([op(slp),[FALSE]]):
  elif i=0 then
    RETURN([op(slp),[TRUE]]):
  elif i<=n then
    RETURN([op(slp),[i]]):
  else
    RETURN([op(slp),[NOT,i-n]]):
  fi:
fi:
[op(slp),op(RandSLPng(n,n+1,n+g))]:
end:

MonoRandSLPng:=proc(n,lo,hi) local g,i,rvs,rff,slp:
g:=hi-lo+1:
if g<1 then print('blorf'): RETURN(FAIL): fi:
rff:=rand(0..1):
if g=1 then
  rvs:=randcomb(lo-1,2):
  RETURN([[1+4*rff(),op(rvs)]]):
fi:
rvs:=rand(floor(g/2)):
i:=max(rvs(),rvs()): # To favor more even distributions on left and right sides of last gate
if i=0 then
  slp:=[op(MonoRandSLPng(n,lo,hi-1)),[1+4*rff(),rand(1..n)(),hi-1]]:
else
  slp:=[op(MonoRandSLPng(n,lo,lo+i)),op(MonoRandSLPng(n,lo+i+1,hi-1)),[1+4*rff(),lo+i,hi-1]]:
fi:
end:

#RandSLPn - generates a random SLP with n variables and g and/or gates
MonoRandSLPn:=proc(n,g) local slp,i:
if n<1 or g<0 then RETURN(FAIL): fi:
slp:=[seq([i],i=1..n)]:
if g=0 then
  i:=rand(-1..n)():
  if i=-1 then
    RETURN([op(slp),[FALSE]]):
  elif i=0 then
    RETURN([op(slp),[TRUE]]):
  else
    RETURN([op(slp),[i]]):
  fi:
fi:
[op(slp),op(MonoRandSLPng(n,n+1,n+g))]:
end:


(* ORIGINAL VERSION
AllSLPng:=proc(n,lo,hi) local g,i,j,vars,rvs,rff,slp,slp2,SLP,S1,S2:
g:=hi-lo+1:
print("lo",lo,"hi",hi):
vars:={seq(k,k=1..n)}:
if g<1 then print('blorf'): RETURN(FAIL): fi:
if g=1 then
  RETURN({seq(seq([[rff,op(rvs)]],rff in 1..10),rvs in choose(hi-1,2))}):
fi:
SLP:={}:
#{seq(seq(seq([op(slp),[rff,op(rvs)]],slp in SLP),rff in 1..10),rvs in choose(hi-1,2))}:
for i from 0 to floor((g-1)/2) do
print(i):
  if i=0 then
   S1:=AllSLPng(n,lo,hi-1):
   SLP:=SLP union {seq(seq(seq([op(slp),[rff,j,hi-1]],j in vars minus {op(2..3,slp[-1])}),slp in S1),rff in 1..10)}:
  else
print(lo,lo+i-1," - ",lo+i,hi-1):
   S1:=AllSLPng(n,lo,lo+i-1):
   S2:=AllSLPng(n,lo+i,hi-1):
   SLP:=SLP union {seq(seq(seq([op(slp),op(slp2),[rff,lo+i,hi-1]],slp in S1),slp2 in S2),rff in 1..10)}:
  fi:
od:
SLP:
end: *)

AllSLPng:=proc(n,lo,hi) local g,i,j,vars,rvs,rff,slp,slp1,slp2,slpn,SLP,SLPn,S1,S2,prefix:
option remember:
g:=hi-lo+1:
print("lo",lo,"hi",hi):
#vars:={seq(k,k=1..n)}:    #Changed to allow for reuse of prior gates
vars:={seq(k,k=1..hi-1)}:
if g<1 then print('blorf'): RETURN(FAIL): fi:
prefix:=[seq([i],i in 1..n),seq([FALSE],j in 1..lo-n-1)]:
SLPn:={}:
SLP:={}:
if g=1 then
  for rff from 1 to 10 do
#    for rvs in choose(n,2) do    #Changed to allow for reuse of prior gates
    for rvs in choose(hi-1,2) do
      slp:=[[rff,op(rvs)]]:
      slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
      if not (slpn in SLPn) then
        SLPn:=SLPn union {slpn}:
        SLP:=SLP union {slp}:
      fi:
    od:
  od:
#print(SLP):
  RETURN(SLP):
fi:
#{seq(seq(seq([op(slp),[rff,op(rvs)]],slp in SLP),rff in 1..10),rvs in choose(hi-1,2))}:
for i from 0 to floor((g-1)/2) do
#print(i):
  if i=0 then
   S1:=AllSLPng(n,lo,hi-1):
#print(S1):
    for rff from 1 to 10 do
      for slp1 in S1 do
        for j in vars minus {op(2..3,slp1[-1])} do
          slp:=[op(slp1),[rff,j,hi-1]]:
          slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
          if not (slpn in SLPn) then
            SLPn:=SLPn union {slpn}:
            SLP:=SLP union {slp}:
          fi:
        od:
      od:
    od:
  else
#print(lo,lo+i-1," - ",lo+i,hi-1):
   S1:=AllSLPng(n,lo,lo+i-1):
   S2:=AllSLPng(n,lo+i,hi-1):
   for rff from 1 to 10 do
     for slp1 in S1 do
       for slp2 in S2 do
        slp:=[op(slp1),op(slp2),[rff,lo+i-1,hi-1]]:
        slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
        if not (slpn in SLPn) then
          SLPn:=SLPn union {slpn}:
          SLP:=SLP union {slp}:
        fi:
       od:
     od:
   od:
  fi:
od:
SLP:
end:


AllSLPn:=proc(n,g) local slp,i,SLP:
if n<1 or g<0 then RETURN(FAIL): fi:
slp:=[seq([i],i=1..n)]:
if g=0 then
  SLP:={[op(slp),[FALSE]],[op(slp),[TRUE]],seq([op(slp),[i]],i=1..n),seq([op(slp),[NOT,i]],i=1..n)}:
  RETURN(SLP):
fi:
SLP:=AllSLPng(n,n+1,n+g):
{seq([op(slp),op(i)],i in SLP)}:

end:

AllMonoSLPng:=proc(n,lo,hi) local g,i,j,vars,rvs,rff,slp,slp1,slp2,slpn,SLP,SLPn,S1,S2,prefix:
option remember:
g:=hi-lo+1:
print("lo",lo,"hi",hi):
#vars:={seq(k,k=1..n)}:    #Changed to allow for reuse of prior gates
vars:={seq(k,k=1..hi-1)}:
if g<1 then print('blorf'): RETURN(FAIL): fi:
prefix:=[seq([i],i in 1..n),seq([FALSE],j in 1..lo-n-1)]:
SLPn:={}:
SLP:={}:
if g=1 then
  for rff in {1,5} do
#    for rvs in choose(n,2) do    #Changed to allow for reuse of prior gates
    for rvs in choose(hi-1,2) do
      slp:=[[rff,op(rvs)]]:
      slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
      if not (slpn in SLPn) then
        SLPn:=SLPn union {slpn}:
        SLP:=SLP union {slp}:
      fi:
    od:
  od:
#print(SLP):
  RETURN(SLP):
fi:
for i from 0 to floor((g-1)/2) do
#print(i):
  if i=0 then
   S1:=AllMonoSLPng(n,lo,hi-1):
#print(S1):
    for rff in {1,5} do
      for slp1 in S1 do
        for j in vars minus {op(2..3,slp1[-1])} do
          slp:=[op(slp1),[rff,j,hi-1]]:
          slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
          if not (slpn in SLPn) then
            SLPn:=SLPn union {slpn}:
            SLP:=SLP union {slp}:
          fi:
        od:
      od:
    od:
  else
#print(lo,lo+i-1," - ",lo+i,hi-1):
   S1:=AllMonoSLPng(n,lo,lo+i-1):
   S2:=AllMonoSLPng(n,lo+i,hi-1):
   for rff in {1,5} do
     for slp1 in S1 do
       for slp2 in S2 do
        slp:=[op(slp1),op(slp2),[rff,lo+i-1,hi-1]]:
        slpn:=BoolToInt(n,SLPntoBool([op(prefix),op(slp)])):
#print(slp,slpn,[op(prefix),op(slp)]):
        if not (slpn in SLPn) then
          SLPn:=SLPn union {slpn}:
          SLP:=SLP union {slp}:
        fi:
       od:
     od:
   od:
  fi:
od:
SLP:
end:


AllMonoSLPn:=proc(n,g) local slp,i,SLP:
if n<1 or g<0 then RETURN(FAIL): fi:
slp:=[seq([i],i=1..n)]:
if g=0 then
  SLP:={[op(slp),[FALSE]],[op(slp),[TRUE]],seq([op(slp),[i]],i=1..n),seq([op(slp),[NOT,i]],i=1..n)}:
  RETURN(SLP):
fi:
SLP:=AllMonoSLPng(n,n+1,n+g):
{seq([op(slp),op(i)],i in SLP)}:

end:

MonoTryRand:=proc(n,g,fn,num) local f,i:
for i from 1 to num do
    f := MonoRandSLPn(n, g):
    if BoolToInt(n, SLPntoBool(f)) = fn then
        RETURN(f):
        break:
    fi:
    if i mod 10000=0 then print(i): fi:
od:
RETURN(nope):
end: