# How do I tell pattern searcher the order in which to search for patterns given in general form?

I have a really long sequence of Symbols inside a function, say nonCommute[a,b,c,e,e,f,g,b,i,j], and I am implementing a recursive algorithm using RepeatedReplace with the rule:

rule = nonCommute[left___,x_,middle___,x_,right___] :> f[Length[middle]]


The right hand side actually isn't f, but is really a sum of more nonCommute with slightly smaller Sequences than the original whose complexity depends on Length[middle]. Consequently, the algorithm goes much much faster if patterns with the shortest midddle___ are matched first, followed middle___ of increasing lengths.

Is it possible to tell the pattern searcher to look for patterns with the shorter middle___ first?

What I have so far

I just do the ugly thing of writing out the first few patterns explicitly in the order I want, and hope middle___ doesn't get too long:

uglyRules = {nonCommute[left___,x_,x_,right___] :> f0[(*...*)],
nonCommute[left___,x_,a1_,x_,right___] :> f1[(*...*)],
nonCommute[left___,x_,a1_,a2_,x_,right___] :> f2[(*...*)],
nonCommute[left___,x_,a1_,a2_,a3_,x_,right___] :> f3[(*...*)],
nonCommute[left___,x_,a1_,a2_,a3_,a4_,x_,right___] :> f4[(*...*)] }


Bonus

It turns out that nonCommute has cyclic property: nonCommute[a,b___] = nonCommute[b___,a]. This means, we can make the algorithm go even faster if we also check for patterns that goes the other way (i.e. wraps around). I have implemented this for the first two of my uglyRules above.

uglyRules = {nonCommute[left___,x_,x_,right___] :> f0[(*...*)],
nonCommute[x_,center___,x_] :> f0[(*...*)],

nonCommute[left___,x_,a1_,x_,right___] :> f1[(*...*)],
nonCommute[a1_,x_,center___,x_] :> f1[(*...*)],
nonCommute[x_,center___,x_,a1] :> f1[(*...*)] }


Can this fact be included in the pattern searcher, too?

Yes it is certainly possible to tell the pattern matcher to search for the shortest pattern.

rule = nonCommute[left___, x_, Shortest[middle__], x_, right___] :> {middle};
nonCommute[a, b, q, b, a] /. rule


results in {q} and

nonCommute[a, b, q, q, b, a] /. rule


results in {q,q}

but you should be somewhat cautious because that does not result in {} and this

nonCommute[a, b, q, q, q, b, a] /. rule


results in just {q}

I need more specific information to understand what your bonus question is. Perhaps you can replace the (* ... *) with something, possibly even something you aren't going to do, but which will be sufficient for others to understand what you want to extract or replace.

EDIT: Revised to replace middle___ (triple underscore) with middle__ (double underscore)

• This is exactly what I need. For some reason, Bill, when I run your examples on my machine (Mathematica 9.0.1), I get the expected result {} for all of them. – QuantumDot Nov 2 '14 at 20:28
• The bonus is pretty easy to understand; I guess I didn't do a good job explaining it in my question. Basically, the elements of nonCommute can be thought to be arranged in a ring (instead of in a line). Then, the distance between repeated elements x_ is shorter of the two sequences around the ring. e.g. in nonCommute[a,b,c,a,d] the rule should trigger on {d} and not {b,c,a}. Get it? – QuantumDot Nov 2 '14 at 20:33
• Using Shortest with a triple underscore pattern is going to give an empty list if you have any adjacent pair of identical items. I had first used double underscore and it looks like some of that incorrectly leaked into my answer. My apologies. Try double and see if that works correctly in all your cases. Next, your cyclic explanation makes much more sense. I don't see a quick simple solution. What if you joined two copies of all your arguments together and looked for patterns in that? Could you correctly extract what you need from that longer list? I'll see if I can think of anything else. – Bill Nov 2 '14 at 21:19

You can directly set a list of replacement rules as Downvalues of your Symbol in the order you prefer:

DownValues[nonCommute] =
{HoldPattern@nonCommute[left___, x_, x_, right___] :>
f0[(*...*)],
HoldPattern@nonCommute[left___, x_, a1_, x_, right___] :>
f1[(*...*)],
HoldPattern@nonCommute[left___, x_, a1_, a2_, x_, right___] :>
f2[(*...*)],
HoldPattern@nonCommute[left___, x_, a1_, a2_, a3_, x_, right___] :>
f3[(*...*)],
HoldPattern@
nonCommute[left___, x_, a1_, a2_, a3_, a4_, x_, right___] :>
f4[(*...*)]};


This order will further be used by the pattern matcher when looking for a pattern which matches an expression with Head nonCommute as reflected in the Definition for nonCommute:

Definition[nonCommute]

nonCommute[left___,x_,x_,right___]:=f0[]

nonCommute[left___,x_,a1_,x_,right___]:=f1[]

nonCommute[left___,x_,a1_,a2_,x_,right___]:=f2[]

nonCommute[left___,x_,a1_,a2_,a3_,x_,right___]:=f3[]

nonCommute[left___,x_,a1_,a2_,a3_,a4_,x_,right___]:=f4[]


Quick check:

nonCommute[a, b, b, b, b, b, b, e]

f0[]


as expected.