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.