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