For a string
s, the Lyndon factorization writes
s as the concatenation of
tn, such that:
For example, given the word
ti is a simple word. That is, it is lexicographically smaller than allof its cyclic shifts.
- the words are in non-increasing order:
t1 >= t2 >= t3 ... >= tn.
banana, the lyndon factorization is:
We can define a notation for writing permutation as:
b; an; an; a;
- Each term in a cycle is written in ascending order.
- Cycles are written in descending order of the first element.
- Single element are ignored.
If we treat it as a string
(7) (2 3) (1 4 5)
the duval algorithm provides the decomposition:
So, we can treat the duval algorithm as a way to recover the permutation given
the raw string. It's a nice way to remember the definition of lyndon
decomposition if nothng else.
7; 23; 145;