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

[Alan Burlison]

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?

Thanks,

-- 
Alan Burlison
--