[r-t] Big searches
Mike Ovenden
mike.ovenden at homecall.co.uk
Mon Jan 7 22:41:37 UTC 2008
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
More information about the ringing-theory
mailing list