1
$\begingroup$

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:

  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.

$\endgroup$

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.