[GAP Forum] Lyndon words in GAP
Gordon Royle
gordon at csse.uwa.edu.au
Thu Jun 3 02:41:25 BST 2004
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).
Then repeat.
If you wanted huge lists of Lyndon words for some purpose, then I am
sure that there are more efficient ways, but this is good if you just
want a few thousand..
On Thu, 2004-06-03 at 07:20, Drew Krause wrote:
> Hello, I'd be interested to see if anyone has done work with generating
> (not necessarily enumerating) Lyndon Words using GAP. I'm attempting it
> myself -- any pointers?
More information about the Forum
mailing list