Todd Rowland
Wolfram Research
Maryland
Registered: Oct 2003
Posts: 115 
Back to Jesse's original question.
One can sometimes use recursive schemes to make an enumeration, following a multiway system. It is general, though not natural.
For instance, for one argument expressions, there are two parts
Head[Argument]
Given a pairing function, Pair[n],
e.g. Pair[n_] := With[{m = Floor[(1+Sqrt[1+8n])/2]},{n(m(m1)/2),(m(m+1)/2)(1+n)}]
expr[0]:=x
expr[1]:=y
expr[n_/;n>=2]:=Module[{a,b},{a,b}=Pair[n2];expr[a][expr[b]]]
will then get you symbolic expressions in the primitives x and y.
More generally, one could write
expr0[n0_, k_]:=Module[{exprk}, exprk[n_]:=f[n]; exprk[n_/;n>=k]:=Module[{a,b},{a,b}=Pair[nk];exprk[a][exprk[b]]]; exprk[n0]]
or
expr[n0_, vars_]:=Module[{exprk,k=Length[vars]}, exprk[n_]:=vars[[n+1]]; exprk[n_/;n>=k]:=Module[{a,b},{a,b}=Pair[nk];exprk[a][exprk[b]]]; exprk[n0]]
which can be used on the right hand side of your symbolic transformations, after the variables have been set from the left hand side.
For instance, with a finite list of variable names (nonempty),
rule[n_,vars_]:= Module[{vars2,a,b,lhs,rhs,rhs0}, {a,b}=Pair[n]; lhs=expr[a,vars]; vars2=Level[lhs,{1},Heads>True]; rhs=expr[b,vars2]; lhs=lhs/.x:(Alternatives@@vars):>pattern[x,blank[]]/.{pattern>Pattern,blank>Blank}; (lhs:>rhs0)/.rhs0>rhs]
One might want to use UnsortedUnion so the results do the right thing when the variable list is reordered.
This might not be the best implementation, but it's the first that comes to mind.
Getting a unique rule is more tricky. Hopefully the following is helpful.
The most obvious thing is to use the nth symbol contained when asking for n symbols, and to renormalize so the zeroth expression is the smallest with n symbols, e.g., a[b][c][d]...
Like the above, one can have two enumeration functions.
expr1[a,n] is the ath expression with symbols coming from the list of the first n variables.
expr2[b,vars,n] is the bth expression with symbols coming from the list of the first n variables, but definitely containing those from vars.
One would write a recursive function for expr2, like
expr2[m_,vars_,n_]:=Module[{a,b,head,vars2,arg}, {a,b}=Pair[m]; head=expr1[a,n]; vars2=Complement[vars,Cases[head,_Symbol,{0,Infinity}]]; arg=expr2[b,vars2,n]; head[arg]] and so on
Report this post to a moderator  IP: Logged
