[GAP Forum] Lyndon words in GAP

[Gordon Royle]

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?