We talked about Nariyana Pandita’s method for iterating over permutations in 1300s India, and also B. R. Heale’s completely different algorithm from 1963 Britain.

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:

- Start with the permutation in ascending order. All elements start looking left.
- Define a
**mobile**element as one which is larger than the element it is looking at. - Find the largest mobile element
**x**. (If no elements are mobile, then you are done iterating.) - Swap
**x**with the element it is looking it. This is the next permutation. - Reverse the direction for
*all elements greater than***x**. - 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).

## 2 thoughts on “Iterating over permutations, part 3 – Steinhaus-Johnson-Trotter algorithm”