Foata's recursive transformation on permutations

Write a permutation in one-line form as a word of distinct integers.

Let $w$ be such a word and let $x$ be an integer not appearing in $w$. Define a word ${\gamma }_x(w)$ as follows.

If $w$ is empty, put ${\gamma }_x(w):=w$. Otherwise inspect the last letter of $w$.

• If the last letter of $w$ is $\le x$, cut $w$ immediately after each letter $\le x$.
• If the last letter of $w$ is $>x$, cut $w$ immediately after each letter $>x$.

This factors $w$ into nonempty blocks $w=w_1\cdots w_r$. For each block $w_j=u_j{y}_j$ with last letter $y_j$, move the last letter to the front and write $\beta (w_j):=y_j{u}_j$. Then set

${\gamma }_x(w):=\beta (w_1)\cdots \beta (w_r)\mathrm{.}$

Now define Foata's transformation $\mathrm{\Phi }$ recursively by

$\mathrm{\Phi }(ϵ):=ϵ,\mathrm{\Phi }(wx):={\gamma }_x(\mathrm{\Phi }(w))x,$

where $ϵ$ is the empty word and $x$ is the last letter of the word $wx$.

This recursively transforms one-line words of permutations, hence permutations.