# Iterating over permutations, part 3 – Steinhaus-Johnson-Trotter algorithm

Yet a third, also completely different, algorithm was discovered by American mathematician Hale Trotter in 1962, and, independently, American mathematician Selmer Johnson in 1963. This is called the Steinhaus–Johnson–Trotter algorithm. I have a PowerShell implementation of this too.

The key concept is to assign each element in the permutation a direction – either left or right. Use < to indicate that the element is looking left, and > to indicate that the element is looking right.

Example: <A <B <C <D

Then the algorithm is follows:

1. Start with the permutation in ascending order. All elements start looking left.
2. Define a mobile element as one which is larger than the element it is looking at.
3. Find the largest mobile element x. (If no elements are mobile, then you are done iterating.)
4. Swap x with the element it is looking it. This is the next permutation.
5. Reverse the direction for all elements greater than x.
6. Repeat steps 2 through 5 until step 3 fails.

Working through the example:

• <A <B <C <D – move D to the left
• <A <B <D <C – move D to the left
• <A <D <B <C – move D to the left
• <D <A <B <C – move C to the left and reverse direction of D
• D> <A <C <B – move D to the right
• <A D> <C <B – move D to the right
• <A <C D> <B – move D to the right
• <A <C <B D> – move C to the left and reverse direction of D
• <C <A <B <D – move D to the left
• <C <A <D <B – move D to the left
• <C <D <A <B – move D to the left
• <D <C <A <B – move B to the left and reverse direction of C and D
• D> C> <B <A – move D to the right
• C> D> <B <A – move D to the right
• C> <B D> <A – move D to the right
• C> <B <A D> – move C to the right and reverse direction of D
• <B C> <A <D – move D to the left
• <B C> <D <A – move D to the left
• <B <D C> <A – move D to the left
• <D <B C> <A – move C to the right and reverse direction of C
• D> <B <A C> – move D to the right
• <B D> <A C> – move D to the right
• <B <A D> C> – move D to the right
• <B <A C> D> – no mobile elements, we’re done

Note that the largest element (in this case, D) goes back and forth, bouncing off of the ends of the permutation.

So (n – 1)/n of the time, the next permutation can be found very quickly (in constant time) by just keeping track of the largest element.

The other 1/n of the time, the largest element is stuck, and a scan is necessary to find the largest mobile element (or lack thereof,) and then to reverse the direction of larger elements. This takes time proportional to n and unsticks the largest element again.

So on average it takes constant time to find the next permutation: O(1) + (O(n)/n) = O(1).