§ Permutations-and-lyndon-factorization

For a string s, the Lyndon factorization writes s as the concatenation of substrings t1, t2, ..., tn, such that:

• each ti is a simple word. That is, it is lexicographically smaller than all of its cyclic shifts.
• the words are in non-increasing order: t1 >= t2 >= t3 ... >= tn.

For example, given the word banana, the lyndon factorization is:

b; an; an; a;

We can define a notation for writing permutation as:

• Each term in a cycle is written in ascending order.
• Cycles are written in descending order of the first element.
• Single element are ignored.

(7) (2 3) (1 4 5)

If we treat it as a string 723145, the duval algorithm provides the decomposition:

7; 23; 145;

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.