ยง 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.