I'm familiar with the Steinhaus–Johnson–Trotter algorithm, which allows for the iterative yielding of permutations of a sequence by performing a single swap per iteration. It has the behavior, however, that it tends to swap elements further along the sequence early in the iteration. For 4 elements, my understanding is that the first 6 permutations will be:
$1,2,3,4$
$1,2,4,3$
$1,4,2,3$
$4,1,2,3$
$4,1,3,2$
$4,3,1,2$
What I'd like to know is whether there is similar iterative algorithm, using relatively simple changes (though obviously can't be single swaps) that yields a sequence:
$1,2,3,4$
$2,1,3,4$
$1,3,2,4$
$2,3,1,4$
$3,1,2,4$
$3,2,1,4$
Per request, here is my attempt at a better definition of the desired result:
- Start with the initial sequence of $n$ elements and yield it.
- For each $i \in \{2..n\}$, then $k \in \{1..i\}$
- Take the element $x_i$ and place it at position $i-k$. We will now consider the first $i$ elements and keep the remaining $n-i$ elements the same.
- Yield all permutations of the remaining $i-1$ elements (using these rules) surrounding the position $i-k$.
Basically the goal is to permute each initial sequence fully before continuing to permute with later elements.
