[r-t] 23-spliced treble dodging major redux
Don Morrison
dfm at ringing.org
Mon May 17 02:30:56 UTC 2010
On Sat, May 1, 2010 at 10:20 AM, Don Morrison <dfm at ringing.org> wrote:
> On Sat, May 1, 2010 at 9:46 AM, Philip Earis <pje24 at cantab.net> wrote:
>> Was this product of simply(!) searching through all 23! arrangements of
>> methods? If so, did you cover the whole search space, how long did it
>> take, and how many compositions did you find? How many more methods could
>> be added before running out of computing resources? And any chance of an
>> 8-part composition?! Lots of questions.
>
> Sort of a random search. Set up to try depth first for an hour, and
> then randomly rearrange the orders of all the nodes in the graph, and
> start again.
I had assumed that a complete search of this space was intractable.
Certainly my experience with ordinary cyclic 7 parts of 23-spliced is
that if you allow any in course, tenors parted leads a full search is
intractable, at least with the technology currently available to me*.
However, on further reflection, I see that this is a much simpler
search space. The branching factor at each node in the tree is half
what it is in a normal such composition, since you never have the
option of bob versus plain: all lead ends in this scheme with randomly
generated methods are plain leads.
With some further investigation I see that it is just at the edge of
what is practical with my current software on current hardware. I
allowed such a search to run to completion, and it required just over
15 days, visiting just under 14 billion nodes†. Faster hardware, or
rejiggering the algorithm to allow it run well on an even moderate
size parallel architecture, which could be very loosely coupled, would
bring this down to something perfectly reasonable for routine use.
The end result produced 55 different compositions. They are appended
to this message. I have appended the note "[best?]" to that which has
the most total 4 bell rollups at the back and front, as that seems
likely to be the metric many folks interested in ringing such a thing
might apply in deciding with is the most attractive arrangement.
I believe these are the only 55 possible true arrangements of these 23
methods with cyclic part heads. However, there may be bugs in my code
causing some to be missed. I'm unaware of any evidence that such bugs
exist, but the aggressive pruning I'm doing certainly provides plenty
of opportunities for me to make programming or logical errors.
I have separately proved each of them, however, and have high
confidence that they are all true. If anyone would like to see them
with the lead heads written out, too, they are all available at
http://ringing.org/random-spliced.html. That seems to voluminous a
presentation even for me to include in an email message, however.
I don't think I've seen this next point mentioned before in the
correspondence, expect perhaps implicitly in Philip's description of
how he generated the methods. Though I doubt those interested in such
a thing will be bothered by it. A peal rung in these twenty-three
methods presumably will be cited as "non-complying" in the Central
Council's analysis of peals, as many (all? I've not carefully checked)
of the methods contain more than four consecutive blows in one place.
* By "technology currently available to me" I'm not principally
thinking of hardware. I think the exponential growth in size of such
a search is such that even a few decades of Moore's Law is unlikely
to make a dent in the problem for a normal cyclic 7 part, as opposed
to the much simpler one involving methods with non-Plain Bob lead
heads and no calls. However, it seems plausible that improved
algorithms might sufficiently prune the search space to make the
search for a normal peal tractable. Though I have no ideas for such
improvements myself right now.
† MBD will I suspect be horrified at something as slow as just under
11K nodes per second. I believe this is the cost of sufficiently
aggressive pruning of the search to bring it down to just having to
explore 14 billion nodes, however. I wonder how a less aggressively
pruned, but faster, search would fare?
A Major = 567.7.5.45.25.256.5.236.2x4.3.2.6.23456.2367.36.23456.36.23.4.234.4.236x25.2.6.34567.567x27
B Major = 347.345.3.6.256.567.56.367.47.2.2347.345.6.56.34.2345.36.56.6.345x27.2347.1.2567.56.27.45.347.34567.3456.4
C Major = 34.36.567.1x27.5.1.4.347.4.2345.4.6x45.2x2.45.2347.34.4.23.7.567.7.67.345.347.7.456
D Major = 56.345.34567.4.2.7x236.7.27.4.2345.3456.34.234.367.56.236.234.25.347.27.34.2367x567.27.6.34567.56.34.67
E Major = 3456.7.345.47.56.25.27.6.2x7.23.6.256.34.567.34.36.2.1.2347x7.367.25.2567.567.1.34.5.3456.4567
F Major = 3.56.34567.6x567.5.3.347.4.2347.345.56.236.36.2347.36.236.6.23.234.34.4.36.2567.25.56.6.5.3.567.2
G Major = 345.567.56.1.5.2.56.6.34.27.347.345.6.256.34.27x6.4.45x34.7.6.7.567.25.47.5.34567.36.27
H Major = 34567.567x4567.2.5.7.23.7.47.347.2345.34.3456.34.5.34.4.234.1.234.34.27.3.256.5.25.67.34567.567.3.456
I Major = 3x3456.4567.256.27.5.1.4.34.234.25.2.56.3456.3.2.256x25.34.2.47.36.256.567.25.4.345.347x27
J Major = 34.7.34567.45x567.7.1.47.27x23.256.23456.234.3.234.6.23456.2345x47.2.23.2567x256.45x7.347.2367
K Major = 3456x567.6.5.27.256.2367.4x347.5.4.2.4.345.36x56.3.234.2.47.36.27.56.5.47.36x36.1
L Major = 3.3456.345.1x25.567.2367.2x34.25.23456.236.4.1.256.234.6.2345x27.47.367.2567.2x47.345.3456.7.2347
M Major = x36.34567.6.7.5.56.23.47.4.47.3.6.2.56.345.256.36.234.25.47.4.2347.236.7.27x1x347.34567.6
N Major = 56.345.34567.4567.56.5.27.1.347x2347.25.23456.4.2.5.36.256.236.45.7.27.7.23.2567.2.25.45.567.3.5.67
O Major = 3456.5.3456.47.56.256.567.2367.234.7.2.345.2.3456.236.23.6.23456.36.23.4.27.2347.6x5x47.345.347.345.2367
P Major = x36.345.456.7.5.567.236.4.7.234.3.36.23456.2.347.4.34.36.345.7.47.2.6.25.567.2567.4.34.5.567.2367
Q Major = 36.345.347.6.56.25.27.6.47x4.23.6.2.234.23.3456.23456.234.45.347.4.234.36.2x256.4567.347.34567.7.67
R Major = 34567.5.347.6.256.27.256.3.34.27x25.4x4.23.36.234.3456.45.347.27.2.1.5.27.2567.67.3.3456.7.23
S Major = 347x345.4.2567.56.5.236.2347.47.27.45.34.2.234.45.236.3456x3.4.2.27.36.2567.27.7.1.567.3456.3.6
T Major = 7x36.4567.25.56.2.6.347.47.347.345.6.34.2.34567.34.6.56.23.2347.234x3.5.7.25.4.3.56.36.4
U Major = 7.34.5.456.256x2.236.4.7.347.5.256.6.56.25.4.6.56.23.27.347.2347.236.256.2567.25.45.3456.3x6
V Major = 3.5.34567.4.56.2567.27.36.47.7.47.23.236.56.6.45.56.36.34.3.4x47.23.7.56.2567.4.5.7.347.6
W Major = 567.36.3456.47.256.27.5.36.234.347-2345.236.234-1-56.3456.1.34.2.34.36.2.2567.25.47.56.3456.347.47
BTIR GJUMVWSDQK EFLPCAHNO 4 56s 0 5678fs 6 8765s 4 8765fs 7 65s
(18234567)
COKJABMUSFLIHDRWVGNTEQ P 2 56s 8 5678fs 1 8765s 4 8765fs 0 65s
(15678234)
CSMAHJPWGRNILQUVF TDEOBK 3 56s 1 5678fs 5 8765s 2 8765fs 5 65s
(14567823)
DGFWEMBSKC NJ ULTPROQA HVI 4 56s 1 5678fs 5 8765s 3 8765fs 2 65s
(18234567)
DH PEK BAFVISLRNUC JGQ WO TM 4 56s 2 5678fs 9 8765s 4 8765fs 3 65s
(14567823)
DILKS OHWMVACJFT QBUNERP G 7 56s 3 5678fs 2 8765s 2 8765fs 4 65s
(15678234)
DISUO TLKAFGMER HJ QCBPN WV 4 56s 7 5678fs 5 8765s 2 8765fs 3 65s
(15678234)
DMPLEW IJQCBNR FVU HKS ATO G 4 56s 3 5678fs 7 8765s 3 8765fs 4 65s
(15678234)
DQLKJF UGTARSHIC OBMWEPNV 1 56s 2 5678fs 1 8765s 4 8765fs 0 65s
(16782345)
ETFIWUBQGMHNRJAVDP SKLCO 3 56s 2 5678fs 3 8765s 5 8765fs 3 65s
(13456782)
EWGDC BUJ AVQLRTOM PFI SHNK 2 56s 3 5678fs 3 8765s 0 8765fs 1 65s
(15678234)
FTJSNVO QMCLE HPUBRKIA GWD 3 56s 4 5678fs 5 8765s 4 8765fs 2 65s
(13456782)
HDURFVSMQWTGJONALPIBEKC 11 56s 5 5678fs 6 8765s 3 8765fs 6 65s
(16782345) [best?]
HNLKSR JQEWCIV GMOAPUBFDT 6 56s 3 5678fs 3 8765s 3 8765fs 4 65s
(14567823)
IF APGES KHWUMCVRNDJT OBQ L 4 56s 3 5678fs 3 8765s 4 8765fs 2 65s
(18234567)
IRKOESJ ULBAH MTGWP DCNVFQ 4 56s 5 5678fs 1 8765s 2 8765fs 2 65s
(13456782)
IWSTCRFO KUPGMDLBEH VNJQ A 9 56s 1 5678fs 4 8765s 3 8765fs 6 65s
(18234567)
JISEOABWKQVFDLTMNPHU GCR 5 56s 2 5678fs 1 8765s 4 8765fs 5 65s
(13456782)
JQRVBD KO NI SHWLFT EM AGC PU 9 56s 1 5678fs 3 8765s 4 8765fs 5 65s
(17823456)
KAMEHWVSLBDIFU JNG OP QRTC 3 56s 1 5678fs 2 8765s 4 8765fs 4 65s
(14567823)
KVAHPC NI WSMJDBU RTLGQOEF 3 56s 1 5678fs 3 8765s 3 8765fs 2 65s
(18234567)
KVQNAC DRE PIFW TOSLHMJ GUB 3 56s 4 5678fs 0 8765s 1 8765fs 5 65s
(13456782)
LGNCAFMSEBQOPHURVKTDIWJ 2 56s 2 5678fs 5 8765s 1 8765fs 2 65s
(13456782)
LK RDEFAGQU ON CITPSBW VMH J 3 56s 1 5678fs 4 8765s 1 8765fs 3 65s
(18234567)
LQAIC PEFSKUGDVB RM TJN OW H 6 56s 1 5678fs 3 8765s 1 8765fs 6 65s
(16782345)
LTJ EQAVU BWHOGDKPFMCISNR 4 56s 0 5678fs 4 8765s 1 8765fs 1 65s
(18234567)
LTO ABFWSJ IDQ GUVRMPH NEKC 5 56s 2 5678fs 5 8765s 6 8765fs 2 65s
(16782345)
MCKLIAP NTOJSRVFW GHEDBU Q 4 56s 1 5678fs 8 8765s 1 8765fs 2 65s
(17823456)
MFTWNALKBRHODG EUJC VISPQ 2 56s 3 5678fs 1 8765s 0 8765fs 1 65s
(14567823)
NSLHMUOJDQKVETAC PB IRGF W 5 56s 7 5678fs 3 8765s 4 8765fs 3 65s
(16782345)
OKTVB SPLQJ DWMAI HCG EFURN 7 56s 3 5678fs 2 8765s 4 8765fs 6 65s
(18234567)
PEJFI QW UVMOBKTLRSCAHGDN 4 56s 2 5678fs 3 8765s 2 8765fs 2 65s
(14567823)
RFGOMPJEU WLVDNTKQSBIAH C 5 56s 1 5678fs 2 8765s 4 8765fs 2 65s
(15678234)
RGNEMPH VSO JIUQCW LFABD TK 4 56s 0 5678fs 1 8765s 5 8765fs 2 65s
(15678234)
RLH IGDJMQC WAF VKOUSP EBNT 3 56s 3 5678fs 7 8765s 3 8765fs 5 65s
(14567823)
RO BNWV HLCK IPSDQUEJF AMTG 7 56s 1 5678fs 1 8765s 2 8765fs 5 65s
(17823456)
RTAQMFGCVWBOSLHKE UPIJ ND 6 56s 5 5678fs 2 8765s 0 8765fs 4 65s
(17823456)
RVCUQDFK IMLPSNB GJA TOWHE 3 56s 6 5678fs 3 8765s 3 8765fs 2 65s
(18234567)
SAFPGTOWVRUK BQLHJEMNCI D 5 56s 4 5678fs 5 8765s 4 8765fs 2 65s
(14567823)
SEJFUB TGNKHQA CV LR OW MPDI 2 56s 5 5678fs 3 8765s 2 8765fs 4 65s
(13456782)
SIR GQKBDJA PMLEFTWHNOCVU 4 56s 5 5678fs 1 8765s 5 8765fs 4 65s
(16782345)
SJLIBND GV QRKUCO TFPWMAHE 4 56s 5 5678fs 0 8765s 3 8765fs 3 65s
(15678234)
SRG MD UTPNWCJHKBI AVLQ OEF 2 56s 2 5678fs 6 8765s 1 8765fs 2 65s
(16782345)
SRTJO UQA LENFICG WPBDM HKV 3 56s 3 5678fs 0 8765s 1 8765fs 4 65s
(17823456)
TUSOHA PKQECMJBG NLIW RVFD 2 56s 1 5678fs 0 8765s 2 8765fs 1 65s
(17823456)
TVGLHPEKFAB MU NI JODQSWCR 6 56s 3 5678fs 2 8765s 0 8765fs 3 65s
(18234567)
UEJRNKDMACOWL IF PB GQSVTH 2 56s 1 5678fs 3 8765s 1 8765fs 6 65s
(15678234)
UMCVRND JTO BQLIFAPG ESKHW 5 56s 2 5678fs 3 8765s 4 8765fs 4 65s
(15678234)
UMVWS DQKEFLPCA HNOBTI RGJ 4 56s 3 5678fs 4 8765s 3 8765fs 3 65s
(15678234)
UPLVDKJEOSAT HGFN IQBCRMW 6 56s 2 5678fs 6 8765s 4 8765fs 4 65s
(13456782)
VE BJI CWKLT ORMDUSPG HNQA F 4 56s 4 5678fs 4 8765s 2 8765fs 3 65s
(13456782)
VOU EJ FIQRHWLKNTS BMPAGD C 6 56s 4 5678fs 0 8765s 8 8765fs 0 65s
(15678234)
WCUDNGLEOA BJRMVK FSTP HI Q 5 56s 2 5678fs 4 8765s 2 8765fs 3 65s
(17823456)
WLKC FVERHJS DIUTOABNPQ GM 5 56s 2 5678fs 1 8765s 2 8765fs 3 65s
(13456782)
WUKAVSGIFTHCLQ MJNPDOBER 5 56s 2 5678fs 3 8765s 5 8765fs 3 65s
(14567823)
--
Don Morrison <dfm at ringing.org>
'The chief gift of nature, he said (never having starved),
is liberty.' -- Will Durant, _The Renaissance_
More information about the ringing-theory
mailing list