[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?
Thanks,
--
Alan Burlison
--
More information about the ringing-theory
mailing list