# [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).

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?

```