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

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:

  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).

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s