Per prima cosa, non sono ancora un programmatore e posso solo capire algoritmi di base scritti in pseudocodice (+ Dijkstra, che è un po 'più difficile di altri, per me). Sono stato attraverso la logica, la teoria degli insiemi, le relazioni, la combinatoria. Attualmente sto studiando la teoria dei grafi.
Puoi darmi una semplice spiegazione su come le parole di Lyndon sono costruite con l'algoritmo di Duval? E come si relaziona a de Bruijn sequwnce e quale pseudocodice viene usato per costruire quella sequenza? Semplice, perché non sono così esperto di matematica nella comprensione di alcune delle notazioni e dei concetti, e anche perché non ho studiato algoritmi e programmazione. Questo problema era nelle mie lezioni di teoria dei grafi ---- > Cicli euleriani e hamiltoniani.
Ho provato a capirlo dal wikipedia , ma l'ho capito solo in alcune parti. Inoltre, lo pseudocodice di GitHub non è comprensibile per me, e non sono riuscito a trovarne un altro. Eccolo:
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()
Sarei grato se potessi mostrarmi con l'esempio, con alcune lettere o numeri, in modo da poterlo comprendere intuitivamente, e con uno pseudocodice più comprensibile, se possibile pesantemente commentato. Grazie.