Permutation on the set of restricted permutations of $\{1,2,\ldots,n\}$ Let $S$ be the set of restricted permutations of $\{1,2,\ldots,n\}$ where $1$ can be permuted to $1,2$ and $n$ can permuted to $n,n-1$ and $i$ can be permuted to $i-1,i,i+1$ for $2\leq i\leq n-1$.
Let $f:S\to S$ be a bijection. Let $\underbrace{f\circ f\circ \cdots f(x)}_{\text{m times}}=x$ be called the orbit of $x$ under $f$ for some $x\in S$.

I am trying to find a bijection $f$ with an orbit as large as possible. I am not sure how to go about finding that. Any ideas?

 A: Obviously, the best case you can hope for is that $m=|S|$, namely that all permutations in $S$ are in one big orbit. Here is an $f$ which achieves this.
From the comments, you know that a permutation $\pi$ is in $S$ if and only if $S$ the cycle structure of $\pi$ only has fixed points and transpositions, and all transpositions are of the form $(i\;\;i+1)$, switching adjacent elements. For completeness, the proof is this. If $\pi(n)=n$, then by induction, $\pi$ restricted to $\{1,\dots,n-1\}$ also has the form described. If $\pi(n)=n-1$, then you must have $\pi(n-1)=n$, since only $n-1$ and $n$ can map to $n$, and we similarly conclude by induction that $\pi$ restricted to $\{1,\dots,n-2\}$ has the claimed form.
Such a permutation can be uniquely represented as an ordered sequence of ones and twos whose total is $n$. For example,
$$
(1\;2)(3)(4)(5\;6)(7\;8)(9)\quad \iff\quad 2,1,1,2,2,1
$$
I will define $f:S\to S$ in terms of these sequences of ones and twos.

Let $s\in S$. To compute $f(s)$,

*

*Find the rightmost $1$ in $s$ which is not at the right end. If no such $1$ exists, then $s=2,2,\dots,2$ or $s=2,2,\dots,2,1$, and we define $f(s)=1,1,\dots,1$.

*

*If that $1$ has a $1$  to its right, then delete both $1$'s, and put a $2$ in their place.

*If that $1$ is has a $2$ to its right, then switch that $1$ and $2$.



*Finally, find all $2$'s to the right of the change just made, and replace each of them with the substring $1,1$.

More succinctly, $f(s)$ is the next string after $s$ in lexicographic order, unless $s$ is the last in this order, in which case $f(s)$ is the earliest string. Here is an example of the complete orbit when $n=6$.




Step
Sequence




1
$1111\color{red}{11}$


2
$111\color{red}{12}$


3
$11\color{red}{12}1$


4
$112\color{red}{11}$


5
$1\color{red}{12}2$


6
$121\color{red}{11}$


7
$12\color{red}{12}$


8
$\color{red}{12}21$


9
$211\color{red}{11}$


10
$21\color{red}{12}$


11
$2\color{red}{12}{1}$


12
$22\color{red}{11}$


13
$222$


14
$111111$



