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:







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:







Per request, here is my attempt at a better definition of the desired result:

  1. Start with the initial sequence of $n$ elements and yield it.
  2. For each $i \in \{2..n\}$, then $k \in \{1..i\}$
  3. 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.
  4. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.