Algoritmo di Duval, parole di Lyndon e sequenza di de Bruijn

2

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.

    
posta Marko Savic 17.01.2017 - 23:40
fonte

1 risposta

1

Il modo più semplice è quello di inserire quanto sopra in un interprete Python. Quindi aggiungi queste righe

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

e stampa

[0]
[1]
[2]

Quindi prova con

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

e stampa

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

Penso che da qui in poi sia chiaro come questo permuta s numeri a lunghezza massima n

Lascio a te il compito di provare altri esempi di permutazione. Puoi aggiungere istruzioni di stampa per capire cosa succede, o ancora meglio lavorare con un debugger abilitato a Python.

    
risposta data 18.01.2017 - 00:58
fonte

Leggi altre domande sui tag