[r-t] 147 TDMM

Tue Sep 28 14:48:46 UTC 2010

Congratulations, Richard, I'm very pleased to see this come to fruition!

Can you give us a list of the plans?

It would be interesting if there were an automated way to analyse the 
plans, and identify the new things.  I'm thinking of something like the 
following.  For any _two_ methods alone, the splicing theory is well 
understood (e.g. 3-lead splices etc.).  A first step would be to weed out 
all those plans that can be explained by any combination of such splices. 
Any ideas of a good way to do this?  Then all those remaining would 
involve grid splices and other more interesting things.  A further 
refinement would be to tease out the structure of these - e.g. identify 
them as "interesting splice X combined with a 3-lead splice".  Any idea 
how to do this?

It would also be interesting to see if the search with singles is 
feasible.

Ander

On Tue, 28 Sep 2010, Richard Smith wrote:

>
> I've spent quite a lot of the last month looking at spliced extents of treble 
> dodging minor.
>
> Thanks to a cunning algorithm (which I shall describe in a moment) designed 
> by Ander which we've been fine-tuning it turns out to be possible to do 
> exhaustive searches over search spaces that I had previously thought were 
> impossibly large.
>
> As a demonstration, I have just done a search for all true extents of minor 
> using just methods from the standard 147 treble dodging minor methods rung 
> with 4ths place lead-end bobs.  I will do some further verification of this 
> result over the next few days, but I believe the number of extents of this 
> form is
>
>  5,862,727,200,079,423,275,554
>
> To put this number into perspective, if I were to produce a booklet listing 
> these in a similar format to that used in the CC's spliced minor collection, 
> then the resulting booklet would be about 5 light-years thick.
>
>
> THE ALGORITHM
>
> There are five main stages to the search algorithm.
>
> First we remove lead splices and lead-end variants from the list of methods. 
> So, for example, we only want to include one of Beverley, Surfleet, Berwick 
> and Hexham.  This reduces the list of methods from 147 to 75.
>
> The second stage is to associate each lead end or lead head row with a 
> method.  Start with a list of the 60 in-course rows with the treble leading 
> -- these will all appear as a l.e. or a l.h., and we need to choose a method 
> for each one, and doing so will join a l.h. to the subsequent l.e.
>
> Suppose some l.e./l.h. rows already have methods chosen.  Of the remaining 
> rows, we call a method 'possible' if
>
>  (i) the l.e. that would be reached by ringing a lead of
>  the method starting at the given l.h. row is not
>  associated with a method; and
>
>  (ii) the lead would be true against all other chosen
>  leads.
>
> Take the row that has the fewest possible methods and, in sequence, try each 
> of its possible methods, recursing. This gives an exhaustive tree search. 
> The result of this is a 'plan' -- a list of which method is rung from each 
> lead, but with no information on how to join the leads up.
>
> Stage two can be speeded up significantly by implementing a form of 
> rotational pruning.  Put the methods in some arbitrary order.  Any method 
> (other than the first one chosen) must not be before the first one chosen in 
> the ordering.  This will remove some but not all rotations and reflections. 
> If you want an accurate count, it's a good idea to check whether a plan is in 
> its canonical rotation and only output it if it is.
>
> The third stage is to do an exhaustive search of ways to join the 30 leads in 
> each plan using 12, 14 or 16 lead end changes.  An normal tree search for 
> compositions will do this fine.  There's no need to check for truth beyond 
> checking for repetition of lead heads and lead ends as this was dealt with in 
> stage two.  For each plan you then have a list of compositions that produce 
> the extent.
>
> Fourth, we remove compositions that include 16 lead ends in London (3-3.4) or 
> Hills (3-34.6) backworks.  This is a little subtle for plans that include one 
> of these backworks and another one -- as 16 lead ends are fine as long as 
> they only occur in the non-London, non-Hills backworks.
>
> A further subtlety arises if rotational pruning was done in stage two. 
> Because there is no clear distinction between rotation and reflection of a 
> plan (because we don't yet know which rows will become a l.h. and which a 
> l.e.), pruning removes both rotations and reflections.  However, going from 
> Carlisle-over to London-over with a 16 l.e. is fine; but going the other way 
> is not.
>
> This gives the complete set of extents.
>
> Fifth, and assuming we want to count them, for each plan, the number of 
> extents is the product of three terms: the number of distinct rotations / 
> reflections (assuming rotational pruning); the number of lead splices (N^n 
> where N is the number of methods in the lead splice set -- 2 or 4 for 
> everything in the 147 -- and n the number of leads of it); and the number of 
> compositions for each plan.  Adding the values for each plan gives the 
> overall total.
>
> For the 147, the five stages took: 4s, 4h 1m, 1h 7m, 16m 44, and 1m 18s.  So 
> the total search time was just under 6h. I've only made an effort to optimise 
> stages two and three (stage five in particular is woefully suboptimal), but 
> given that's where most of the time is spent, that seems reasonable.  I 
> reckon that without too much work the search could be reduced to under 4h -- 
> maybe even under 3h.
>
>
> THE EXTENTS
>
> Because the search first finds plans, and the number of plans (modulo 
> rotation) is a fairly managable 4614, it's fairly easy to get a good idea of 
> what's there.  And a quick scan through the list of plans shows that there 
> are some interesting plans that are new (at least to me).  I'll give a 
> breakdown of what's there in a later email.
>
> RAS
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net
>