[r-t] Big searches

[Mike Ovenden]

That loop looks exactly like mine (except that for MUG, items 4 and 6 amount 
to the same thing).  I guess the difference lies in what we each do for item 
1.

Mine's basically the FKM algorithm (see below) with some pruning for 
falseness.  Here's what happens when I put in a length constraint (20 
eights) and comment out the falseness checking.  Obviously the touches 
aren't of much interest...

 6 pppppp
 12 pppppppppppp
 18 pppppppppppppppppp
 20 ppppppppppppppbbppbb
Completed
Depth InternalNodes Branches
 1 1 2
 2 2 3
 3 3 5
 4 5 8
 5 8 14
 6 14 23
 7 23 41
 8 41 71
 9 71 127
 10 127 226
 11 226 412
 12 412 747
 13 747 1377
 14 1377 2538
 15 2538 4720
 16 4720 8800
 17 8800 16510
 18 16510 31042
 19 31042 58636
 20 58636 111013
Totals
InternalNodes Branches Comps
 125303 236315 775

You can look up the third column in the On-Line Encyclopedia of Integer 
Sequences to discover that it's A062692 - the Number of irreducible 
polynomials over F_2 of degree at most n.  Doesn't mean anything much to me, 
but I gather that it's the same as the number of binary pre-necklaces of 
length n, which is what I expect.

Since this is one of the means I used to validate my program, you can 
probably understand my focus on exact values.  Not that it matters as long 
as you know what you're doing and I (think I) know what I'm doing!


Regards,
Mike


>From gordon at csse.uwa.edu.au  Thu Jun  3 02:41:25 2004
From: gordon at csse.uwa.edu.au (Gordon Royle)
Date: Thu Jan  5 13:04:19 2006
Subject: [GAP Forum] Lyndon words in GAP
In-Reply-To: <40BE60C4.80100 at mindspring.com>
References: <40BE60C4.80100 at mindspring.com>
Message-ID: <1086226885.20359.7.camel at ekaltadeta>

The FKM algorithm is very easy to implement, and one can extract the
Lyndon words from the output. I gave it to my students as an assignment
question so could give you up to 8 different programs to do it.

However these are not trying to be super-efficient, but just
implementing the algorithm using GAP lists to represent the words..

Proceed as follows to generate length n Lyndon words over an alphabet of
k symbols (0,1,... k-1).

Start with w = [0,0,...,0]

Find the largest index i such that w[i] < k-1

Increase w[i] by 1, and then replace the remainder of the list (w[i+1]
..w[n]) by as many copies of w[1]...w[i] as will fit.

Then

- if i = n, the word is a Lyndon word,
- if i | n, the word is a periodic necklace,
- otherwise the word is a pre-necklace (prefix of some longer
necklace).



----- Original Message ----- 
From: "Mark Davies" <mark at snowtiger.net>
To: <ringing-theory at bellringers.net>
Sent: Sunday, January 06, 2008 11:09 AM
Subject: [r-t] Big searches


> Mike Ovenden writes,
>
>> So I suppose your node count is pretty much my branch count, but I'm
>> wondering how come we're 1% apart.
>
> I don't think this is very surprising - there are several ways to write an
> inner loop of a search engine, and various places to put the counter
> increment, depending on whether it is before or after various tests for
> inclusion of the current node. My code appears to do the following:
>
> Loop:
>  1. Use current call to load pointer to next node.
>  2. Is next node null? (Implies this call not allowed from current node)
> Yes -> jump out to try next call.
>  3. Next node is valid, increment node pointer.
>  4. Check to see if node has been visited before. Yes -> jump out to try
> next call.
>  5. Check to see if composition too long with new node. Yes -> jump out.
>  6. Check to see if node is false against anything visited before. Yes ->
> jump out.
>  7. Node OK, mark it as visited.
>  8. Prepare for next iteration, jump to Loop top.
>
> This is a very simplistic version of the loop, with no pruning, however it
> shows that I count all nodes considered for inclusion, even if they may be
> false or already included in the comp.
>
> MBD
>
> _______________________________________________
> ringing-theory mailing list
> ringing-theory at bellringers.net
> http://bellringers.net/mailman/listinfo/ringing-theory_bellringers.net