[r-t] Big searches

[Mike Ovenden]

Your understanding looks pretty much spot on.  I'd guessed you must have 
something to eliminate pre-necklaces that aren't actually necklaces, having 
looked at a few .sfN files in detail.

Actually, I implemented the algorithm from *your* description after you 
extolled its virtues long ago!  It was only later that I identified it with 
the FKM algorithm, as a result of finding how many nodes it visited and 
feeding that into the Encyclopedia of Integer Sequences (even then I had to 
do a bit of digging).  I think the reason I looked into it that much was 
because of your comments on the SMC %complete estimate.  Talking of which, 
maybe one of the serious mathematicians out there would care to provide an 
efficient algorithm for determining the number of pre-necklaces of length n 
<= (lexicographically) some given pre-necklace.

I did try comparing node counts for at least one other length, but didn't 
get precise agreement.  I even started to wonder about your definition of 
Mnode, but that didn't help - I guess it's 1000000 nodes!

Mike

----- Original Message ----- 
From: "Mark Davies" <mark at snowtiger.net>
To: <ringing-theory at bellringers.net>
Sent: Monday, January 07, 2008 10:55 PM
Subject: [r-t] Big searches


> Mike Ovenden writes,
>
>> Mine's basically the FKM algorithm (see below) with some pruning for
>> falseness.
>
> WTF is the FKM algorithm?? Could it be that the difference between my node
> counts and yours is that you are using a super-cool-esoteric-TLA-mathmo
> algorithm and I'm just using a bog-standard rotationally-sorted search? 
> :-)
>
> Looking at your mate Gordon's explanation, there does appear to be some
> familiar bits. I could almost imagine that a "Lyndon word" is a one-part
> composition, and a "periodic necklace" is a multipart, but I might be
> horribly wrong. A "pre-necklace" looks like something you'd drop because
> it's a multipart you've already found with a better prefix. I seem to
> remember something like that in my rotational sort, bit hacky but it 
> works.
>
> Have you tried running SMC32 on those short lengths of MUG, to see if we
> start agreeing at any stage?
>
> MBD
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net