[r-t] Bobs only Erin Triples (was: Composition search)
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:
> 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...
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
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?
More information about the ringing-theory