Duval's algorithm, Lyndon words and de Bruijn sequence

Question

First, I am not a programmer (yet) and I can only understand basic algorithms written in pseudocode (+Dijkstra, which is a little harder than others, for me). I have been trough logic, set theory, relations, combinatorics. Currently, I am studying graph theory.

Can you give me a simple explanation on how Lyndon words are constructed with Duval's algorithm? And how is that related to de Bruijn sequwnce and what pseudocode is used to construct that sequence? 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. This problem was in my graph theory lessons ----> Eulerian and Hamiltonian cycles.

I tried understanding it from the wikipedia, but I only understood it in parts. Also, 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, and with more understandable pseudocode, heavy commented if possible. Thanks.

Answer 1

The easiest is to stuff the above in a Python interpreter. Then append these lines

for w in LyndonWords(3,1):
  print w

and it prints

[0]
[1]
[2]

Then try with

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

and it prints

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

I think from here on it's clear how this permutes s numbers to max length n

I leave it up to you to try out more permutation examples. You may add print statements to understand what happens, or even better you work with a Python capable debugger.