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