Lyndon words and Duval's algorithm

Question

Can you give me an simple explanation on how are Lyndon words constructed with Duval's algorithm? Simple, because I am not so math proficient in understanding some of the notation and concepts, and also because I haven't study algorithms and programming, yet (this problem was in my graph theory lessons).

I tried understanding it from the wikipedia and this link , but I only understood it in parts. Also, this pseudocode from GitHub is not understandable to me, and I couldn't find another. Here it is:

    def LyndonWords(s,n):
    """Generate nonempty Lyndon words of length <= n over an s-symbol alphabet.
The words are generated in lexicographic order, using an algorithm from
J.-P. Duval, Theor. Comput. Sci. 1988, doi:10.1016/0304-3975(88)90113-2.
As shown by Berstel and Pocchiola, it takes constant average time
per generated word."""
    w = [-1] # set up for first increment
    while w:
        w[-1] += 1 # increment the last non-z symbol
        yield w
        m = len(w)
        while len(w) < n: # repeat word to fill exactly n syms
            w.append(w[-m])
        while w and w[-1] == s - 1: # delete trailing z's
            w.pop()

I would be thankful if you could show me by example, with some letters or numbers, so that I can intuitively comprehend it.

Answer 1

LyndonWords create a generator object given s and n:

type(LyndonWords(3,2))
# generator

To see what the code does, we can iterate over this generator and print each of the value:

for word in LyndonWords(3, 2):
    print(word)

# [0]
# [0, 1]
# [0, 2]
# [1]
# [1, 2]
# [2]

These lists are derived as follows. I only explain the computation of the first two, commenting step by step what the code does.

w = [-1]

The argument w is initialized to the list [-1]. This assignment is only evaluated once.

while w:

While the list w is not empty (i.e., w != []), do the following:

w[-1] += 1

Add one to the last element of w. The value of w is now [0].

yield w

Create an element for the generator. The first element will be [0], this is what we have printed above.

m = len(w)
while len(w) < n:
    w.append(w[-m])

Compute the size of w, and extend w to a size n by appending to it the value w[-m] as many times as needed. m is 1, n is 2, and w is [0], so the new value of w is [0, 0].

while w and w[-1] == s - 1:
   w.pop()

While w is not an empty list and its last element equals s - 1, remove the last element. The value of w, which is [0, 0] at this point, does not satisfy the last test, so we do not execute w.pop() and we go back to the outer while.

while w

The value of w ([0, 0]) is not an empty list, so we execute the body of the while loop.

w[-1] += 1
yield w

Add one to the last element of w. The value of w is now [0, 1]. Create another element for the generator. The second element will be [0, 1], which is what we have printed above.

From the above explanation, it should hopefully be clear how the next elements of the generator are created. Note that these elements are not all created when calling LyndonWords. They are computed one by one on the fly, only when requested. (This is one of the features of generators in Python.)