[r-t] Bobs only Erin Triples (was: Composition search)

[Richard Smith]

Ian Broster wrote:

> You can remove rotations of the same touch from the search 
> space by using the path from the root to the current node 
> as your starting point for the next recursion.

Oh, there are lots of optimisation you can make, and the 
code fragment I gave there is not something I'd ever use for 
anything but the simplest of search.  If you look in the 
table_search class in the Ringing Class Library, you'll see 
it does rotational pruning, for example.

The skeletal algorithm I gave works fine for a multi-part 
search because you factor out the part-end group when you 
generate your multiplication table.  (Obviously you divide 
840 by the part-end group size.)  But pruning rotations in 
that situation is not as simple as you suggest because the 
particular choice of part-end group already eliminates most 
but not all of the rotations.  If you want full pruning, the 
obvious strategy is to repeat the search for every possible 
conjugate group and do full rotational pruning on each in 
the manner you suggested.  But the gain from doing this is 
not large -- rather less than an order of magnitude for the 
sort of searches we're talking about.

> Obviously, an easy optimization is to do this in a loop 
> rather than a recursive call.  That more than doubles the 
> speed,

I'm sorry, but that's utter bollocks.  If your recursive 
implementation is twice as slow as a loop-based solution, 
you've done it wrong, or you're using a ridiculously 
high-level language.  The cost of a function call is simply 
not that high.

RAS