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

Alan Burlison alan.burlison at gmail.com
Tue Nov 24 17:19:43 UTC 2015

On 24/11/2015 14:04, Philip Earis wrote:

> For a comprehensive background on bobs only Stedman triples, see this
> webpage by Philip Saddleton (often referred to as PABS), which gives
> a good historical context:
> http://myweb.tiscali.co.uk/saddleton/stedman/bdp.htm
> If you want to see some more recent correspondence linked to Erin,
> take a look at the (freely-accessible) archives of this list, eg this
> thread from June 2012 which involves Andrew Johnson, PABS, Eddie
> Martin etc...
> http://www.bellringers.net/pipermail/ringing-theory_bellringers.net/2012-June/010581.html

Thanks for the links, I'll read them this evening.

As an aside: I've only been ringing a couple of months so I can't even 
physically ring methods yet ;-) but I'm intrigued by the computational 
aspects of methods. So however simple you make things you almost 
certainly aren't talking down to me :-)

> Of course, reinventing the wheel should be avoided. At the most naive
> level bobs only Erin triples is still far too huge for a brute force
> search...an extent (5040 rows) will consist of 840 divisions of 6
> changes ("sixes"), each of which can either be plain (p) or bobbed
> (b), and 2^840 is unfathomably vast. (Of course, huge pruning of the
> search space is possible).

I think such huge pruning is the only way of making the problem 
tractable. Graph search is a problem that's been around for a long time 
and is key to activities such as DNA sequencing so there's no end of 
literature on the topic.

I don't think the search space is as vast as you suggest (although it's 
still big), if I'm understanding the problem correctly, the last row of 
any particular 6-change division has to be the same as the first row of 
the division that follows it - or is there another change between the two?

My initial thoughts would be to generate all possible p and d divisions 
and then perform a tree search using those. As soon as a particular 
sequence of divisions is known to be false then any other subsequences 
that are the same can immediately pruned from the sub-tree. That should 
make the search space significantly smaller as well.

Bearing in mind I have no background in the the ringing theoretic 
aspects of this problem and that I'm approaching it purely as a CS 
search space problem, I'd like to make some observations about the 
problem space that may well be incorrect - please be appropriately 
understanding :-)

I've looked at the code in the C++ ringing library, it appears to check 
for falseness by comparing each row to all the rest that follow it 
within a division. That can be improved on by caching the rows within 
each division in sorted order rather than ringing order and then doing a 
merge sort or binary search when comparing against other blocks.

Given a set of pre-generated divisions, when considering which ones may 
follow a particular sequence of divisions we can immediately rule out 
any that are already in the sequence as the result would be false. The 
same is true if addition of a new division to a sequence results in a 
subsequence that we have already established is false.

That can be done in a hierarchical way, for example if we have 
established that any given sequence is true, we can cache all it's 
ordered sub-sequences as being true. For example, if (A,B,C) is true 
then (A,B) and (B,C) are true.

Are there any constraints or other simplifying assumptions I've missed?


Alan Burlison

More information about the ringing-theory mailing list